Your Ad Here

Thursday, May 13, 2010

Decimal Number to Roman Numeral Conversion Version 3

Two previous posts showed how to convert a decimal value to a Roman numeral.  The first method was very clunky and elementary, the second method is considerably more efficient.

It ocurred to me, after designing and implementing the second algorithm, that if you're willing to sacrifice a bit more memory space for a table, then there's a faster way to convert from decimal values to Roman numeral notation.  The following code shows an implementation of the algorithm in VB .NET.  I call it the MCXI algorithm due to the values of the four rows in the table. There are some funny things going on between the 0 based indexing used in accessing array data and 1 based indexing used in the MID function used for parsing the input string that you may need to address this if you use a different programming language.


    Private Sub btnConvert_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnConvert.Click

        ' Algorithm MCXI
        ' Written by: Erik Oosterwal
        ' Written on: 1-21-2008
        '
        ' Routine to convert Decimal values to Roman Numeral notation.  This algorithm uses a table to store
        '   all the standard Roman Numeral notation for each digit in each Base-10 digit position (ones, tens,
        '   hundreds, thousands).  Each Decimal character is then evaluated to find its magnitude and extract
        '   the corresponding Roman Numeral notation for that value and prepend it to the output string.
        '
        ' This routine does not check for proper usage - the input is not checked for valid numeral characters
        '   and it does not check to verify that the values are positive values between 1 and 4000.  To make
        '   function robust, you check put checks in place for these conditions.

        'Store the Roman codes for each Decimal digit.
        Dim strRoman(,) As String = {{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}, _
                                     {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}, _
                                     {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}, _
                                     {"", "M", "MM", "MMM", "MMMM", "", "", "", "", ""}}

        Dim strOutput As String = Nothing               ' Initialize the output string to blank.
        Dim intLoopI As Integer = Nothing               ' Counter used for the Loop
        Dim intStrLength As Integer = Nothing           ' The length of the input string.

        intStrLength = Len(Me.txtInput.Text)            ' Find out how many digits are in the input number (magnitude).

        For intLoopI = intStrLength To 1 Step -1        ' MID function uses 1 based indexing for the string pointer.

            strOutput = strRoman(intStrLength - intLoopI, Val(Mid$(Me.txtInput.Text, intLoopI, 1))) & strOutput

        Next

        Me.txtOutput.Text = strOutput

    End Sub


As you can see, algorithm number three (MCXI Algorithm) executes the loop a maximum of 4 times and uses no division or multiplication. This should speed up the run time a great deal over the previous two listings.

1 comment:

EarlyChristianityBlog said...

Hey Eric,
I have stumbled onto your Roman numeral conversions in doing a bit of fun research. I have noted that not just you but other programmers who do the conversions do not seem to be aware of the natural algorithmic pattern the Roman numerical system deploys. Yet, the rules are simple. It is an decimal system interpolated (with the halving V, L, D markers) so that in the notation no decimal letter (I,X,C,M) digit can occur more than than three times in succession. Surely then, we can devise a better algorithm than one tabulating numerical values of the letters or their combination and emulating the hand-motions on the abacus ! I challenge you to devise modulo-9 based method which calculates the letters based directly on the notation rules. You are not allowed a table giving the numbers of the letters (they are implied by the decimal placement !!!! in a translation table (simply "MDCLXVI"). Try it ! I am sure you'll have fun with this!