1

Possible Duplicate:
How to convert integer value to Roman numeral string?

Back in my college days, when learning C and all i had come across a question of representing a year in its corresponding Roman Numeral form. There was no solution in that text, as it was among some extra questions to ponder. All i could think of was using modulus operator and a bunch of ifs. I was wondering if some one could give me a proper solution. A simple algorithm or explanation of the logic used would be appreciated.

Community
  • 1
  • 1
midhunhk
  • 5,560
  • 7
  • 52
  • 83
  • I dont want the code as specified in the above link, i want a simple explanation of the logic. – midhunhk Jun 29 '11 at 06:06
  • 1
    The logic is apparent from the code. There are only a few to several lines of code in there. Plus it's explained in the answer and comments. Feel free to ask if there is anything specific you don't understand. – Jean-François Corbett Jun 29 '11 at 06:35

1 Answers1

5

Here's logic for numbers less than 4,000. (See below for what to do above that.) There's a basic, 4-step algorithm that is applied at each level of magnitude.

  1. Determine the number of thousands in the number: floor(number/1000). Output that many "M"s and subtract that many thousands from the number. At this point, the number is less than 1,000.

  2. If the number is >= 900, output "CM" and subtract 900.

  3. If the number is >= 500, output "D" and subtract 500.

  4. If the number is >= 400, output "CD" and subtract 400.

At this point, the number is guaranteed to be < 400. We follow a similar pattern to reduce the number to less than 40:

  1. Determine the number of hundreds in the number, output that many "C"s and subtract that many hundreds from the number. At this point, the number is less than 100.

  2. If the number is >= 90, output "XC" and subtract 900.

  3. If the number is >= 50, output "L" and subtract 50.

  4. If the number is >= 40, output "XL" and subtract 40.

At this point, the number is guaranteed to be < 40. We repeat exactly the same logic using "X", "IX", "V", and "IV". We finish by using the number (guaranteed to be < 4) as the count of how many "I"s to output.

For larger numbers, the logic is still the same, we just use the standard symbols with bars on top. Each bar represents 1,000 times the value without that bar. (So V with a bar is 5,000, etc.)

Ted Hopp
  • 232,168
  • 48
  • 399
  • 521
  • Seems like using recursion would be easier to implement here, right? – midhunhk Jun 29 '11 at 06:57
  • 1
    Yes, there is a certain mindless repetitiveness here that is reminiscent of recursion :). There's probably as much bookkeeping to recursion as there is to just unrolling the logic, at least for numbers in the range that Roman numerals were designed to handle. – Ted Hopp Jun 29 '11 at 14:37