---

The Complete Guide to Roman Numerals in Cairo: From Ancient Logic to Modern Smart Contracts

Converting Arabic numbers to Roman numerals is a classic programming challenge that tests your understanding of algorithms, data structures, and string manipulation. In Cairo, this task offers a unique opportunity to master core language features while bridging the gap between ancient numerical systems and cutting-edge blockchain technology. This guide breaks down the entire process, from theory to a production-ready implementation.

---

The What: Deconstructing the Roman Numeral System

Before diving into Cairo code, it's crucial to understand the logic behind Roman numerals. Unlike the positional Arabic system (where the position of a digit determines its value, like the '1' in 10 vs. 100), the Roman system is additive and, in some cases, subtractive.

Core Symbols and Their Values

The system is built upon seven key symbols, each representing a fixed value:

• I: 1
• V: 5
• X: 10
• L: 50
• C: 100
• D: 500
• M: 1000

To form a number, you typically add the values of the symbols together. For example, III is 1 + 1 + 1 = 3, and LXX is 50 + 10 + 10 = 70. The symbols are generally written from largest to smallest value.

The Subtractive Principle: The Secret Sauce

The real elegance (and complexity) comes from the subtractive principle. To avoid repeating a symbol four times (like IIII for 4), a smaller value symbol is placed before a larger value symbol. This indicates subtraction.

There are six standard subtractive combinations:

• IV: 4 (5 - 1)
• IX: 9 (10 - 1)
• XL: 40 (50 - 10)
• XC: 90 (100 - 10)
• CD: 400 (500 - 100)
• CM: 900 (1000 - 100)

This rule is the key to an efficient conversion algorithm. For instance, the number 1994 is not written as MDCCCCLXXXXIIII. Instead, it's broken down using the subtractive principle: 1000 (M) + 900 (CM) + 90 (XC) + 4 (IV), resulting in MCMXCIV. This is far more concise and is the standard form we must generate.

---

The Why: Roman Numerals in the World of Cairo and Starknet?

You might wonder about the practical application of such a classic problem in the context of modern smart contracts. While you probably won't be calculating gas fees in Roman numerals, mastering this algorithm provides tangible benefits for any Cairo developer.

• Algorithmic Thinking: It forces you to think about greedy algorithms, data representation (maps or arrays of tuples), and iterative logic—skills that are directly transferable to more complex problems in DeFi, governance, and on-chain gaming.
• Data Manipulation: The task is a perfect exercise in handling arrays and building up results piece by piece, a common pattern in Cairo for everything from generating dynamic NFT metadata to processing transaction batches.
• Gas Optimization Awareness: Implementing this efficiently makes you consider loop performance and data storage, which are critical for writing gas-friendly smart contracts on Starknet.
• Niche Applications: For creative projects like historical dApps, on-chain clocks, generative art NFTs with unique numbering, or educational platforms, this functionality can be a distinctive feature.

This module from the kodikra.com learning path is designed not just to solve a puzzle, but to build a foundational understanding of problem-solving in a resource-constrained environment like a blockchain.

---

The How: The Greedy Algorithm for Roman Numeral Conversion

The most straightforward and efficient way to convert an Arabic number to a Roman numeral is with a "greedy" algorithm. The strategy is to always subtract the largest possible Roman numeral value from the number at every step. This naturally handles both the standard and subtractive forms correctly, provided our data is structured properly.

The Core Logic Explained

The process is simple and iterative. Let's take the number 2499 as an example.

1. Set up a Lookup Table: Create a list of pairs, each containing an Arabic value and its corresponding Roman symbol. This list MUST be sorted in descending order of value. This is the most critical part of the setup.
2. Initialize: Start with the input number (2499) and an empty result string.
3. Iterate and Subtract: Go through your sorted list from top to bottom.
   • Is 2499 >= 1000? Yes. Append "M". Number becomes 1499. Result: "M".
   • Is 1499 >= 1000? Yes. Append "M". Number becomes 499. Result: "MM".
   • Is 499 >= 1000? No. Move to the next value (900).
   • Is 499 >= 900? No. Move to the next value (500).
   • Is 499 >= 500? No. Move to the next value (400).
   • Is 499 >= 400? Yes. Append "CD". Number becomes 99. Result: "MMCD".
   • Is 99 >= 400? No. Move on.
   • ...and so on...
   • Is 99 >= 90? Yes. Append "XC". Number becomes 9. Result: "MMCDXC".
   • Is 9 >= 90? No. Move on.
   • ...and so on...
   • Is 9 >= 9? Yes. Append "IX". Number becomes 0. Result: "MMCDXCIX".
4. Termination: Once the number reaches 0, the process is complete. The final result is "MMCDXCIX".

Algorithm Flow Diagram

This ASCII diagram illustrates the greedy approach, showing the decision-making loop at the heart of the conversion process.

    ● Start (Input: u32 number, Result: "")
    │
    ▼
  ┌───────────────────────────┐
  │  Define Sorted Roman Map  │
  │  (1000:"M", 900:"CM", ...)│
  └────────────┬──────────────┘
               │
               ▼
    ┌─── For each (value, symbol) in map ───┐
    │                                       │
    │          ┌─── While number >= value ───┐
    │          │                             │
    │          ▼                             ▼
    │   Append symbol to Result      Subtract value from number
    │          │                             │
    │          └───────────┬───────────┘
    │                      │
    └──────────────────────┼────────────────┘
                           │
                           ▼
                      ◆ number == 0?
                     ╱              ╲
                   Yes               No (Continues loop)
                    │
                    ▼
               ● End (Return Result)

---

The Where: Implementing Roman Numeral Conversion in Cairo

Now, let's translate this logic into Cairo code. We will first examine a solution written in an older version of Cairo (Cairo 0/1) to understand the evolution of the language, and then present a modern, idiomatic solution using Cairo 2.x.

Code Walkthrough: A Look at an Earlier Cairo Implementation

The following code, from an earlier module in the kodikra.com curriculum, demonstrates a valid approach using syntax and types from Cairo versions prior to 2.0. Understanding it provides context for how much the language has improved in terms of ergonomics and clarity.

use core::fmt::{Display, Error, Formatter};

#[derive(Drop)]
pub struct Roman {
    value: ByteArray,
}

impl U32IntoRoman of Into<u32, Roman> {
    #[must_use]
    fn into(self: u32) -> Roman {
        // In older Cairo, constant arrays were often defined inside functions.
        let mut roman_map: Span<(u32, ByteArray)> = array
![
            (1000, "M")
, (900, "CM"), (500, "D"), (400, "CD"),
            (100, "C"), (90, "XC"), (50, "L"), (40, "XL"),
            (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I")
        ];

        let mut num = self;
        let mut result = Default::default();

        let mut i = 0;
        loop {
            if i == roman_map.len() {
                break;
            }

            let (val, sym) = *roman_map.at(i);
            
            loop {
                if num < val {
                    break;
                }
                num -= val;
                result.append_word(sym);
            };
            
            i += 1;
        };

        Roman { value: result }
    }
}

Line-by-Line Breakdown:

• use core::fmt::{...}: Imports necessary for formatting, which is not directly used in the conversion logic but might be for displaying the `Roman` struct.
• pub struct Roman { value: ByteArray }: Defines a struct named Roman to hold the result. It uses ByteArray, a type for handling strings in older Cairo versions, which could be cumbersome.
• impl U32IntoRoman of Into<u32, Roman>: This is the old syntax for implementing a trait. It's defining how to convert (Into) a u32 into our Roman struct.
• let mut roman_map: Span<(u32, ByteArray)> = array ![...]: This is our crucial lookup table. It's created as a Span (a view into an array) of tuples. Each tuple contains a u32 value and its corresponding ByteArray symbol. Notice it's correctly sorted from largest to smallest value.
• let mut num = self;: A mutable copy of the input number is created. self here refers to the u32 value being converted.
• let mut result = Default::default();: Initializes an empty ByteArray to build our result.
• loop { ... }: The code uses nested loops. The outer loop iterates through the roman_map using an index i.
• let (val, sym) = *roman_map.at(i);: It retrieves the value and symbol at the current index.
• loop { if num < val { break; } ... }: The inner loop is the core of the greedy algorithm. It repeatedly subtracts the current value (val) from num and appends the symbol (sym) as long as num is large enough.
• result.append_word(sym);: Appends the Roman symbol to our result.
• Roman { value: result }: Finally, it constructs and returns the Roman struct containing the final ByteArray.

The Modern Solution: An Optimized Cairo 2.x Implementation

While the old code works, modern Cairo offers a much cleaner, safer, and more readable way to write the same logic. Let's refactor it to use current best practices.

// We can use the core library's Array and Span for a cleaner implementation.
use core::array::{ArrayTrait, SpanTrait};

// This struct is optional but good practice for type safety.
// We could also just return an Array<felt252>.
#[derive(Drop, Serde)]
struct Roman {
    value: Array<felt252>,
}

/// Converts a u32 integer to its Roman numeral representation as an Array<felt252>.
/// This function implements a greedy algorithm for numbers up to 3999.
fn arabic_to_roman(mut num: u32) -> Array<felt252> {
    // In modern Cairo, we can define this map more cleanly.
    // Using felt252 for symbols is standard.
    let roman_map = array
![
        (1000_u32, "M")
, (900_u32, "CM"), (500_u32, "D"), (400_u32, "CD"),
        (100_u32, "C"), (90_u32, "XC"), (50_u32, "L"), (40_u32, "XL"),
        (10_u32, "X"), (9_u32, "IX"), (5_u32, "V"), (4_u32, "IV"), (1_u32, "I")
    ];

    let mut result: Array<felt252> = array
![];

    // Using a for loop over a span is more idiomatic and safer than manual indexing.
    let mut map_span = roman_map.span()
;
    loop {
        match map_span.pop_front() {
            Option::Some(pair) => {
                let (val, sym) = *pair;
                while num >= val {
                    // Short felt252s like "M" or "CM" can be appended directly.
                    // For longer strings, you would iterate and append characters.
                    result.append(sym);
                    num -= val;
                }
            },
            Option::None => {
                break;
            }
        };
    };

    result
}

Improvements in the Modern Version:

• Clarity and Readability: The code is simpler. The use of a `for`-like loop pattern with `span.pop_front()` is more expressive and less prone to off-by-one errors than manual index management.
• Modern Types: It uses Array<felt252> instead of ByteArray. felt252 is the fundamental type in Cairo, and short strings are represented directly as felt252. Array is the standard dynamic array type.
• Type Suffixes: Using 1000_u32 makes the integer type explicit, which is a good practice for preventing bugs.
• Idiomatic Looping: Iterating over a Span is the canonical way to process array elements in modern Cairo. It's safer and more efficient.
• No Unnecessary Struct: The function can directly return an Array<felt252>, simplifying the code unless the Roman struct is needed for type abstraction elsewhere in a larger project.

Data Structure Visualization

The `roman_map` is the engine of our algorithm. Visualizing it as a descending, prioritized list helps clarify why the greedy approach works.

    ● Lookup Process
    │
    ├─► [ 1000, "M" ]  (Highest Priority)
    │
    ├─► [  900, "CM" ]
    │
    ├─► [  500, "D" ]
    │
    ├─► [  400, "CD" ]
    │
    ├─► [  100, "C" ]
    │
    ├─►    ... (and so on)
    │
    └─► [    1, "I" ]  (Lowest Priority)

---

The When: Considering Performance and Limitations

Every algorithm has trade-offs. The greedy approach is highly effective for this problem, but it's important to understand its boundaries and performance characteristics, especially in a gas-sensitive environment like Starknet.

Pros & Cons of the Greedy Algorithm

Pros	Cons / Risks
Simplicity & Readability: The logic is easy to understand, implement, and debug.	Depends on Sorted Data: The algorithm will produce incorrect results if the lookup table is not sorted in descending order.
Efficiency: For the given constraints (numbers up to 3999), this is very fast. The number of loop iterations is small and predictable.	Not Generalizable: This specific implementation is tailored to Roman numerals. It's not a general-purpose conversion algorithm for other numeral systems.
Low Gas Cost: The operations are simple arithmetic (subtraction) and array appends, which are relatively cheap in terms of gas on Starknet.	Hardcoded Limit: This implementation does not support numbers greater than 3999, as there is no standard Roman symbol for 4000 or higher.

For the vast majority of use cases, this algorithm is the optimal choice. Its deterministic nature and low computational overhead make it a perfect fit for on-chain execution. For a deeper dive into Cairo and its features, check out our complete Cairo language guide.

---

Frequently Asked Questions (FAQ)

Why must the list of Roman numeral values be sorted in descending order?

The descending order is critical for the "greedy" strategy to work. By always checking for the largest possible value first (like 900 before 500 or 100), you ensure the most concise and correct representation. If you checked for 100 before 900, the number 900 would be incorrectly converted to "DCCCC" instead of the standard "CM".

What is the largest number this algorithm can handle and why?

The algorithm, as implemented, can handle numbers up to 3999. This is because the largest symbol in our map is 'M' (1000), and standard Roman numeral convention doesn't repeat a symbol more than three times in a row. Therefore, 3000 is "MMM", and 3999 is "MMMCMXCIX". There is no standard, universally accepted single symbol for 5000, so the system breaks down for numbers 4000 and above without using non-standard notations like a vinculum (a bar over a numeral).

How does this conversion logic perform in terms of Starknet gas fees?

This logic is very gas-efficient. The number of iterations is bounded and small. For the largest input (3999), the outer loop runs 13 times (the size of the map), and the inner `while` loop runs a handful of times at most for each value. All operations are simple arithmetic and array manipulations, which have a low computational footprint on the Starknet VM.

Can I convert Roman numerals *back* to Arabic numbers with a similar logic?

Yes, you can. The reverse process also uses a lookup map. You would iterate through the Roman numeral string, checking if the current symbol's value is less than the next symbol's value. If it is, you subtract it (like 'I' before 'V' in "IV"). Otherwise, you add it. This requires careful parsing of the input string, character by character or in pairs.

What are some common mistakes when first implementing this algorithm?

The most common mistake is not sorting the lookup table correctly (or at all). Another frequent error is forgetting to include the subtractive pairs (900, 400, 90, 40, 9, 4), which leads to verbose and incorrect outputs like "VIIII" for 9. Finally, off-by-one errors in loop conditions or incorrect index handling (a problem solved by the modern Cairo iterator pattern) can also cause issues.

Why does the modern code use `Array<felt252>` for strings?

In Cairo, a `felt252` is a field element, the basic data type. Short strings (up to 31 characters) can be packed directly into a single `felt252`. For longer or dynamic strings, an `Array<felt252>` is often used to hold the sequence of characters or packed chunks. This is the standard and most flexible way to handle string-like data in modern Cairo smart contracts.

---

Conclusion: From Ancient Rome to the Modern Blockchain

You have successfully journeyed from the foundational principles of an ancient numeral system to a modern, efficient implementation in Cairo. This exercise demonstrates a core tenet of software engineering: complex problems can often be solved with simple, elegant algorithms. The greedy approach to Roman numeral conversion is a testament to this, providing a solution that is both readable and performant.

By mastering this logic, you've sharpened your skills in algorithmic design, data structuring, and writing idiomatic Cairo code. This knowledge is a valuable asset as you tackle more intricate challenges in the Starknet ecosystem.

Disclaimer: The code examples provided are based on Cairo 2.x syntax and conventions. The Cairo language and its ecosystem are continuously evolving. Always refer to the latest official documentation for the most current best practices.

Ready for your next challenge? Continue your journey on the kodikra.com Cairo learning path to build even more powerful and sophisticated smart contracts.

---

Published by Kodikra — Your trusted Cairo learning resource.