Sunday, February 5, 2012

When in Rome...

Let's start with the problem of adding Roman numerals, from Programming Praxis:
Your task is to write a function that takes two roman numerals (character strings) as input and returns their sum as a roman numeral as output. Be sure that input can be given in either the additive or subtractive forms of Roman numerals; give output using the subtractive form. What is add-roman("CCCLXIX", "CDXLVIII")?
Roman numerals are a natural development from tallying and finger counting. Some examples:
  • 1 = I = extend one finger on right hand
  • 2 = II = two fingers
  • 3 = III = three fingers
  • 4 = IIII = four fingers
  • 5 = V = right thumb
  • 6 = VI = right thumb and one finger
  • 9 = VIIII = right thumb and four fingers
  • 10 = X = one finger on left hand
  • 15 = XV = one finger on left hand and thumb on right hand
  • 50 = L = thumb on left hand
  • 77 = LXXVII = left thumb and two fingers, right thumb and two fingers
  • 99 = LXXXXVIIII = extend all fingers on both hands
  • 100 = C = out of fingers!
  • 500 = D
  • 1000 = M
These examples all take the additive form of Roman numerals, which I call "old style".  A later innovation, driven by desire for compactness is to use position and subtraction to avoid repetition of 4 symbols in a row.

Key cases:
  • 4 = IIII = IV
  • 9 = VIIII = IX
  • 40 = XXXX = XL
  • 90 = LXXXX = XC
  • 400 = CCCC = CD
  • 900 = DCCCC = CM
Please note that this more compact form is a step backwards in terms of computation: The beauty of tallying (and additive notations) is that you can add by simple collecting like symbols and then reducing.  For example:

LXXXX + LXXXX 
= LL XXXXX XXX (collect the like symbols)
= C L XXX  (since LL reduces to C and XXXXX reduces to L)

In other words, addition with (additive) Roman numerals is simpler than conventional arabic addition:

90 + 90 = 180 (in this case)

There's less to remember, and no carrying to worry about.  The full reduction rules form an easy pattern:
  • IIIII -> V
  • VV -> X
  • XXXXX -> L
  • LL -> C
  • CCCCC -> D
  • DD -> M
Easy, and forming a logical pattern.  Of course, ultimately, the arabic place-value system is far superior for an array of reasons, but for adding and subtracting small positive numbers, tallying and its extensions are arguably better.

By contrast, I know of no simple, direct way to perform addition with subtractive roman numerals, and would normally convert to another representation -- arabic or additive -- do the computation there, and then convert back.

Here's some Python code for inter-converting between both styles of Roman numerals and the more familiar arabic representation, plus addition of additive Roman numerals using reduction rules -- the more authentic method -- and addition of subtractive Roman numerals via arabic form.

Notes on the code:
  • I use a rule-based form so that the same algorithm (with different rule-sets for additive and subtractive conventions) converts Roman numerals <-> arabic
  • The practice of iteratively reducing a number to zero or chomping through a string until there is nothing left while building up the result is a common pattern
  • There's no error-checking yet for ill-formed roman numerals: we're avoiding that pain for the moment.
Ideas for extensions and explorations: 
  1. Subtraction and multiplication of additive Roman numerals via reduction rules
  2. Devise an augmented Roman numeral system with six more symbols for five thousand, ten thousand, fifty thousand, one hundred thousand, five hundred thousand, and one million; extend the code and do some sums.
  3. Explore the connections between Roman numerals and the (Roman) abacus

No comments:

Post a Comment