Doing Math with Roman Numbers

Problem

You want to convert between Arabic and Roman numbers, or do arithmetic with Roman numbers and get Roman numbers as your result.

Solution

The simplest way to define a Roman class that acts like Fixnum is to have its instances delegate most of their method calls to a real Fixnum (as seen in the previous recipe, Recipe 2.13). First we'll implement a container for the Fixnum delegate, and methods to convert between Roman and Arabic numbers:

	class Roman
	 # These arrays map all distinct substrings of Roman numbers
	 # to their Arabic equivalents, and vice versa.
	 @@roman_to_arabic = [['M', 1000], ['CM', 900], ['D', 500], ['CD', 400],
	 ['C', 100], ['XC', 90], ['L', 50], ['XL', 40], ['X', 10], ['IX', 9],
	 ['V', 5], ['IV', 4], ['I', 1]]
	 @@arabic_to_roman = @@roman_to_arabic.collect { |x| x.reverse }.reverse

	 # The Roman symbol for 5000 (a V with a bar over it) is not in
	 # ASCII nor Unicode, so we won't represent numbers larger than 3999.
	 MAX = 3999

	 def initialize(number)
	 if number.respond_to? :to_str
	 @value = Roman.to_arabic(number)
	 else
	 Roman.assert_within_range(number)
	 @value = number
	 end
	 end

	 # Raise an exception if a number is too large or small to be represented
	 # as a 
Roman number.
	 def 
Roman.assert_within_range(number)
	 unless number.between?(1, MAX)
	 msg = "#{number} can't be represented as a Roman number."
	 raise RangeError.new(msg)
	 end
	 end

	 #Find the Fixnum value of a string containing a Roman number.
	 def Roman.to_arabic(s)
	 value = s
	 if s.respond_to? :to_str
	 c = s.dup
	 value = 0
	 invalid = ArgumentError.new("Invalid Roman number: #{s}")
	 value_of_previous_number = MAX+1
	 value_from_previous_number = 0
	 @@roman_to_arabic.each_with_index do |(roman, arabic), i|
	 value_from_this_number = 0
	 while c.index(roman) == 0
	 value_from_this_number += arabic
	 if value_from_this_number >= value_of_previous_number
	 raise invalid
	 end
	 c = c[roman.size..s.size]
	 end

	 #This one's a little tricky. We reject numbers like "IVI" and
	 #"IXV", because they use the subtractive notation and then
	 #tack on a number that makes the total overshoot the number
	 #they'd have gotten without using the subtractive
	 #notation. Those numbers should be V and XIV, respectively.
	 if i > 2 and @@roman_to_arabic[i-1][0].size > 1 and
	 value_from_this_number + value_from_previous_number >=
	 @@roman_to_arabic[i-2][1]
	 raise invalid
	 end

	 value += value_from_this_number
	 value_from_previous_number = value_from_this_number
	 value_of_previous_number = arabic
	 break if c.size == 0
	 end
	 raise invalid if c.size > 0
	 end
	 return value
	 end

	 def to_arabic
	 @value
	 end
	 #Render a Fixnum as a string depiction of a 
Roman number
	 def to_ 
roman
	 value = to_arabic
	 Roman.assert_within_range(value)
	 repr = ""
	 @@arabic_to_roman.reverse_each do |arabic, roman|
	 num, value = value.divmod(arabic)
	 repr << roman * num
	 end
	 repr
	 end

Next, we'll make the class respond to all of Fixnum's methods by implementing a method_missing that delegates to our internal Fixnum object. This is substantially the same method_missing as in Recipe 2.13 Whenever possible, we'll transform the results of a delegated method into Roman objects, so that operations on Roman objects will yield other Roman objects.

	# Delegate all methods to the stored integer value. If the result is
	# a Integer, transform it into a Roman object. If it's an array
	# containing Integers, transform it into an array containing Roman
	# objects.
	def method_missing(m, *args)
	 super unless @value.respond_to?(m)
	 hex_args = args.collect do |arg|
	 arg.kind_of?(Roman) ? arg.to_int : arg
	 end
	 result = @value.send(m, *hex_args)
	 return result if m == :coerce
	 begin
	 case result
	 when Integer
	 Roman.new(result)
	 when Array
	 result.collect do |element|
	 element.kind_of?(Integer) ? Roman.new(element) : element
	 end
	 else
	 result
	 end
	 rescue RangeError
	 # Too big or small to fit in a Roman number. Use the original number
	 result
	 end
	end

The only methods that won't trigger method_missing are methods like to_s, which we're going to override with our own implementations:

	 def respond_to?(method_name)
	 super or @value.respond_to? method_name
	 end

	 def to_s
	 to_ 
roman
	 end

	 def inspect
	 to_s
	 end
	end

We'll also add methods to Fixnum and String that make it easy to create Roman objects:

	class Fixnum
	 def to_roman
	 Roman.new(self)
	 end
	end

	class String
	 def to_roman
	 Roman.new(self)
	 end
	end

Now we're ready to put the Roman class through its paces:

	72.to_roman # => LXXII
	444.to_roman # => CDXLIV
	1979.to_roman # => MCMLXXIX
	'MCMXLVIII'.to_roman # => MCMXLVIII

	Roman.to_arabic('MCMLXXIX') # => 1979
	'MMI'.to_roman.to_arabic # => 2001

	'MMI'.to_roman + 3 # => MMIV
	'MCMXLVIII'.to_roman # => MCMXLVIII
	612.to_roman * 3.to_roman # => MDCCCXXXVI
	(612.to_roman * 3).divmod('VII'.to_roman) # => [CCLXII, II]
	612.to_roman * 10000 # => 6120000 # Too big
	612.to_roman * 0 # => 0 # Too small

	'MCMXCIX'.to_roman.succ # => MM

	('I'.to_roman..'X'.to_roman).collect
	# => [I, II, III, IV, V, VI, VII, VIII, IX, X]

Here are some invalid Roman numbers that the Roman class rejects:

	'IIII'.to_roman
	# ArgumentError: Invalid Roman number: IIII
	'IVI'.to_roman
	# ArgumentError: Invalid Roman number: IVI
	'IXV'.to_roman
	# ArgumentError: Invalid Roman number: IXV
	'MCMM'.to_roman
	# ArgumentError: Invalid Roman number: MCMM
	'CIVVM'.to_ 
roman
	# ArgumentError: Invalid 
Roman number: CIVVM
	-10.to_roman
	# RangeError: -10 can't be represented as a Roman number.
	50000.to_roman
	# RangeError: 50000 can't be represented as a Roman number.

 

Discussion

The rules for constructing Roman numbers are more complex than those for constructing positional numbers such as the Arabic numbers we use. An algorithm for parsing an Arabic number can scan from the left, looking at each character in isolation. If you were to scan a Roman number from the left one character at a time, you'd often find yourself having to backtrack, because what you thought was "XI" (11) would frequently turn out to be "XIV" (14).

The simplest way to parse a Roman number is to adapt the algorithm so that (for instance) "IV" as treated as its own "character," distinct from "I" and "V". If you have a list of all these "characters" and their Arabic values, you can scan a Roman number from left to right with a greedy algorithm that keeps a running total. Since there are few of these "characters" (only 13 of them, for numbers up to 3,999), and none of them are longer than 2 letters, this algorithm is workable. To generate a Roman number from an Arabic number, you can reverse the process.

The Roman class given in the Solution works like Fixnum, thanks to the method_missing strategy first explained in Recipe 2.13. This lets you do math entirely in Roman numbers, except when a result is out of the supported range of the Roman class.

Since this Roman implementation only supports 3999 distinct numbers, you could make the implementation more efficient by pregenerating all of them and retrieving them from a cache as needed. The given implementation lets you extend the implementation to handle larger numbers: you just need to decide on a representation for the larger Roman characters that will work for your encoding.

The Roman numeral for 5,000 (a V with a bar over it) isn't present in ASCII, but there are Unicode characters U+2181 (the Roman numeral 5,000) and U+2182 (the Roman numeral 10,000), so that's the obvious choice for representing Roman numbers up to 39,999. If you're outputting to HTML, you can use a CSS style to put a bar above "V", "X", and so on. If you're stuck with ASCII, you might choose "_V" to represent 5,000, "_X" to represent 10,000, and so on. Whatever you chose, you'd add the appropriate "characters" to the roman_to_arabic array (remembering to add "M_V" and "_V_X" as well as "_V" and "_X"), increment MAX, and suddenly be able to instantiate Roman objects for large numbers.

The Roman#to_arabic method implements the "new" rules for Roman numbers: that is, the ones standardized in the Middle Ages. It rejects certain number representations, like IIII, used by the Romans themselves.

Roman numbers are common as toy or contest problems, but it's rare that a programmer will have to treat a Roman number as a number, as opposed to a funny-looking string. In parts of Europe, centuries and the month section of dates are written using Roman numbers. Apart from that, outline generation is probably the only real-world application where a programmer needs to treat a Roman number as a number. Outlines need several of visually distinct ways to represent the counting numbers, and Roman numbers (upper- and lowercase) provide two of them.

If you're generating an outline in plain text, you can use Roman#succ to generate a succession of Roman numbers. If your outline is in HTML format, though, you don't need to know anything about Roman numbers at all. Just give an

1. tag a CSS style of list-style-type:lower-roman or list-style-type:upper-roman. Output the elements of your outline as
2. tags inside the
   1. tag. All modern browsers will do the right thing:
      1. Primus
      2. Secundis
      3. Tertius
       

      See Also

      • Recipe 2.13, "Simulating a Subclass of Fixnum"
      • An episode of the Ruby Quiz focused on algorithms for converting between Roman and Arabic numbers; one solution uses an elegant technique to make it easier to create Roman numbers from within Ruby: it overrides Object#const_ missing to convert any undefined constant into a Roman number; this lets you issue a statement like XI + IX, and get XX as the result (http://www.rubyquiz.com/quiz22.html)