Roman Numeral to Decimal Conversion - Algorithm 2

A second method for converting Roman numerals to decimal numbers has been posted on the Computer Science 101 website.

According to the article on that site, the algorithm boils down to this:

1. Set the character pointer to point at the right-most character.
2. Set the value of the summing variable to be the value of the current character.
3. Move the character pointer to the left one step.
4. Compare the value of the current character to the previous character:
5. If the current character's value is the same or larger than the previous character, ADD its value to the sum.
6. Otherwise, if the current character's value is smaller than the previous character, SUBTRACT its value from the sum.
7. Repeat steps 3-6 until the left-most character has been evaluated.

 

You can get a full listing of a function employing this algorithm written in Visual Basic on the Computer Science 101 website.

 

 

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.

Roman Numeral to Decimal Conversion

You can find algorithms for creating Roman Numerals from decimal values here and here. 

In this post we'll take a look at the first of two algorithms for accepting a Roman Numeral and converting it back into a decimal value.

The basic rules for this algorithms are:

Start at the left-most character in the Roman Numeral string and work your way to the last character one character at a time. Add the value of the current character to the total. If the current character has a larger value than the previous character, then subtract 2x the value of the previous character from the total.

For instance the Roman Numeral XIX has a decimal value of 19.  We start at the first character, 'X', and add 10 to the running total; our total is now 10.  We evaluate the second character, 'I' and add 1 to our running total, which now becomes 11.  We evaluate the third character, 'X', and add 10 to our total; our total is now 21, but...  Because the current character has a larger value than the previous character we must subtract 2x the value of the previous character, 1, from the total bringing the new total to 19.  There are no more characters so we stop.

Function Roman2Decimal(strInput as string) as integer

   Dim intValues() as integer                ' Reserve space for an array.
   Dim intLoopI as integer = nothing         ' Initialize the loop counter to 0.
   Dim intTotal as integer = nothing         ' Clear the total.
   Dim intPreviousPointer as integer = 99999 ' Set the value of the previous pointer to some MAX value.
   Dim intCurrentPointer as integer = nothing  ' This will hold the value of the current Roman Numeral character.

   intValues(M) = 1000             ' This array addressing method
   intValues(D) = 500              '  assumes that the language you
   intValues(C) = 100              '  are using allows you to use
   intValues(L) = 50               '  values other than integer values
   intValues(X) = 10               '  to access data in an array.
   intValues(V) = 5
   intValues(I) = 1

   For intLoopI = 0 to (len(strInput)-1)   ' Assuming 0 indexing...

      intCurrentPointer = intValues(mid$(strInput,intLoopI,1)) ' Get the value of the current Roman Numeral character
      intTotal = intTotal + intCurrentPointer                  ' Add the value to the total.

      If intCurrentPointer > intPreviousPointer then       ' If the current value is larger than the previous, then
         intTotal = intTotal - (2 * intPreviousPointer)    '  subtract twice the value of the previous character from the total.
      EndIf

      intPreviousPointer = intCurrentPointer      ' Move the value of the current character to be the
                                                  '  value of the previous character and get then next one.

   Next

   Roman2Decimal = intTotal

End Function

Infix to RPN Notation

Here is a limited algorithm for converting infix notation to RPN notation. The algorithm has no way of handling unary minuses (indicating negative numbers) nor does it deal with functions such as SIN(), COS(), SQR(), etc. I describe one way of handling unary minus in the comments of the program listing below and will alter the code to handle those as well as sines, cosines, square roots, etc. at a later date. In the mean time if you need an infix to RPN converter, this should handle most of your needs.

Parsing from left to right, any numeric value we encounter or any alphanumeric string that could be interpreted as a variable is sent directly to the output, including decimal points.

When we encounter anything other than numbers or letters (or a decimal point), we do the following:

Append a token separator to the output string (in our case a comma.)

If we encounter an open parenthesis, that parenthesis is pushed to a FILO stack.

If we encounter a closing parenthesis, we discard it and pop operators from the stack to the end of the output string until we come to an open parenthesis. The open parenthesis is then also discarded.

If we encounter a low priority operator (+ or -) then we must first pop all operators (+, -, *, /, ^) from the stack to the end of the output string until the stack is empty or we encounter an open parenthesis and then push the low priority operator on to the stack.

If we encounter a medium priority operator (* or /) then we must first pop any medium or high priority operators (*, /, ^) from the stack to the end of the output string until the stack is empty or we encounter a low priority operator (+ or -) or we encounter an open parenthesis, then push the medium priority operator on to the stack.

If we encounter a high priority operator (^) we pop all other high priority operators from the stack to the end of the output string then push the new high priority operator to the stack.

Once all the input character have been processed, we pop operators off the stack until it's empty.


The listing below shows a Visual Basic implementation of the algorithm:

'
'   Infix to RPN - program to convert infix notation to
'       RPN notation.  Operands are separated by commas, to
'       use a different separation character change the
'       line where txtSeparator is initialized.  The operator
'       stack has been set to an upper limit of 100 operators,
'       if you expect to have input strings with more than 100
'       operators (heaven forbid...) increase the size of
'       txtStack in the Dim statement.
'
'       This routine does not handle unary minus signs.  To allow
'       unary minus signs two additional changes must be made.  In the
'       Low Operator case (+, -) we must check to see if the previous
'       input character was an alphanumeric.  If it IS alphanumeric
'       we treat the minus as a normal binary operator.  If it is NOT
'       alphanumeric, then we append a zero and token separator to the
'       output string, and push a special unary minus character to the
'       stack, which has an operator value equal to ^.  You can use the
'       tilde "~" as the unary minus character since it's not being used
'       for anything else.  I'll make this changes to the routine at a
'       later date.
'
'   Written by -    Erik Oosterwal
'   Started on -    Nov. 14, 2005
'   Completed on -  Nov. 15, 2005

    Dim txtSeparator, txtStack(100), txtCharacter As String     ' Declare all variables
    Dim intPointer, intStackPointer As Integer                  ' used in the routine

    txtSeparator = ","      ' Set the token separator to a comma
    intPointer = 1          ' Start by looking at the first character in the input string
    intStackPointer = 1     ' Start the operator stack at 1
    txtOutput.Text = ""     ' Clear the output sting

    While intPointer <= Len(txtInput.Text)                      ' As long as there's characters in the string
    
        txtCharacter = Mid$(txtInput.Text, intPointer, 1)       ' get the next character.
        
        Select Case txtCharacter
        
            Case "0" To "9", ".", "A" To "Z", "a" To "z"        ' Numbers and variables get appended
                txtOutput.Text = txtOutput.Text + txtCharacter  '   directly to the output string.
                
            Case "("
                txtStack(intStackPointer) = txtCharacter        ' Open parentheses get pushed on the stack
                intStackPointer = intStackPointer + 1
                
            Case ")"                                                    ' If we find a closing parenthesis
                While intStackPointer > 1 And _
                        txtStack(intStackPointer - 1) <> "("            ' Clear the stack until we
                    txtOutput.Text = txtOutput.Text + txtSeparator + _
                        txtStack(intStackPointer - 1)                   ' get to the opening parenthesis.
                    intStackPointer = intStackPointer - 1
                Wend
                intStackPointer = intStackPointer - 1       ' Decrease the stack pointer to overwrite the opening parenthesis.
                
            Case "+", "-"                                               ' Lowest operators
                txtOutput.Text = txtOutput.Text + txtSeparator          ' Append a token separator to the output string.
                
' If there are any operators on the stack AND they're higher or equal valued than + and -, then...
'   pop them off the stack and append them to the output string.
                While intStackPointer > 1 And _
                        txtStack(intStackPointer - 1) <> "("
                    txtOutput.Text = txtOutput.Text + _
                        txtStack(intStackPointer - 1) + txtSeparator
                    intStackPointer = intStackPointer - 1
                Wend
                txtStack(intStackPointer) = txtCharacter            ' Push the low operator on the stack.
                intStackPointer = intStackPointer + 1
                
            Case "*", "/"                                           ' Medium operators
                txtOutput.Text = txtOutput.Text + txtSeparator      ' Append a token separator to the output string.
                
' If there are any operators on the stack and they're higher or equal valued than * and /, then
'   pop them off the stack and append them to the output string.
                While intStackPointer > 1 And _
                        (txtStack(intStackPointer - 1) = "*" Or _
                        txtStack(intStackPointer - 1) = "/" Or _
                        txtStack(intStackPointer - 1) = "^")
                    txtOutput.Text = txtOutput.Text + _
                        txtStack(intStackPointer - 1) + txtSeparator
                    intStackPointer = intStackPointer - 1
                Wend
                txtStack(intStackPointer) = txtCharacter        ' Push the medium operator on the stack.
                intStackPointer = intStackPointer + 1
                
            Case "^"                                            ' High operators
                txtOutput.Text = txtOutput.Text + txtSeparator  ' Append a token separator to the output string.
                While intStackPointer > 1 And _
                        txtStack(intStackPointer - 1) = "^"
                    txtOutput.Text = txtOutput.Text + _
                        txtStack(intStackPointer - 1) + txtSeparator
                    intStackPointer = intStackPointer - 1
                Wend
                txtStack(intStackPointer) = txtCharacter        ' Push the high operator on the stack.
                intStackPointer = intStackPointer + 1
                
' There is no default case included in this routine.  Any characters not explicitly taken care
'   of by the cases will be ignored as whitespace.  Some characters, such as x, #, and others
'   that are used to denote binary, hex, octal, etc. numbers could be taken care of in the first
'   case where numeric and alpha tokens are handled.  It's ok to ignore spaces, tabs and other
'   white space.
        
        End Select
    
        intPointer = intPointer + 1             ' Set the pointer to look at the next character
        
    Wend
    
'   All the input characters have been taken care of, now it's time to clear the stack.
'
    While intStackPointer > 1                               ' As long as there's still operators on the stack
        txtOutput.Text = txtOutput.Text + txtSeparator + _
            txtStack(intStackPointer - 1)                   ' Take one off and append it to the output string
        intStackPointer = intStackPointer - 1               ' look at the previous operator
    Wend

End Sub

Decimal Value to Roman Numeral - Algorithm 2

If you haven't seen the earlier algorithm to change Decimal Values to Roman Numerals you can read that blog here: Decimal Values to Roman Numeral Algorithm 1.


The following code represents a shorter algorithm that should be easy enough to understand. Algorithm 2 does away with the cumbersome IF statements from the previous algorithm and wraps up all the conversions in one WHILE loop. This function the same principle as that used in the previous algorithm, but instead of hard coding all the values of the Roman Numeral characters and pairs into separate IF and WHILE clauses, the values and characters are stored in a couple of arrays and referenced in a single WHILE loop. I have not compared the speeds of the two algorithms demonstrated here and in Decimal Values to Roman Numeral Algorithm 1. The speed tests will be covered in a later blog, but for now, here's the code written in VB .NET:

DECIMAL to ROMAN Algorithm 2

    Private Sub cmdConvert_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles cmdConvert.Click

        ' Declare and initialize all variables.  Roman Numerals and their standard combinations
        '   are stored in strRoman.  The corresponding values are stored in intDecimal.

        Dim strRoman() As String = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
        Dim intDecimal() As Integer = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
        Dim intInput As Integer = Nothing           ' Numeric representation of the input field.
        Dim intTemp As Integer = Nothing            ' Used to store the magnitude of each decimal digit.
        Dim intPointer As Short = 0                 ' Pointer to the Roman and Decimal arrays, starts at the first cell.
        Dim intCountI As Short = Nothing            ' Temporary variable used for loops.

        intInput = CInt(txtInput.Text)              ' Convert the string in the input field to an integer.
        txtOutput.Clear()                           ' Clear the contents of the output field.

        While intInput > 0                                  ' Check to see if intInput still has any value left in it.
            intTemp = intInput \ intDecimal(intPointer)     ' See how many of the currently selected value can fit in the remaining input.

            For intCountI = 1 To intTemp
                txtOutput.Text += strRoman(intPointer)      ' Append a number of Roman Characters depending on the value of intTemp.
            Next

            intInput -= intTemp * intDecimal(intPointer)    ' Subtract the value of the characters that were appended to output from the input.
            intPointer += 1                                 ' Move the pointer to the next cell of the arrays.
        End While

    End Sub

You can download a ZIP file with all the VB .NET project files and an executable using this algorithm here. You can also see several other algorithm implementations at the Computer Science 101 website.

Convert Floating Point Decimal Values to Floating Point Binary Representation

A visitor to this site send me an email asking if it were possible to use the Numeric Base Conversion algorithm to convert fractions between bases.  I thought it would be pretty straight forward to implement the change to the general algorithm, but found it was easier just to make a single purpose algorithm to convert from decimal to binary, since that was specifically what he asked for.  As time allows, I'll update the algorithm to make it general purpose to convert fractions between any two bases.


This algorithm borrows from the general Numeric Base Conversion algorithm, but it has been simplified to only convert from base 10 to base 2, and an additional portion that converts the fractional part of the input number to a binary fraction has been added.


Binary fractions are a bit tricky to work with.  Some values convert easily, such as 0.5, 0.375, and 0.75, which are 0.1, 0.011, and 0.11, respectively, in binary form.  Other fractional values, which are easily displayed in base 10, become long strings of seemingly random bits.  For instance, 1/10 = 0.1 (base 10) = 0.000110011001100110... (base 2), and 1/3 = 0.33333... (base 10) = 0.010011001100110011... (base 2), and 1/100 = 0.01 (base 10) = 0.000000101000111101... (base 2).


If you are already familiar with binary notation, you recognize that each binary digit represents a power of 2.  Starting at the least significant bit and moving towards the most significant bit, the bits represent 1, 2, 4, 8, 16, 32, 64, 128, etc.  Just as decimal fraction digits represent the inverses of the powers of 10: 1/10, 1/100, 1/1000, etc, binary fractional bits represent the inverses of the powers of 2:  1/2, 1/4, 1/8, 1/16, etc., which are 0.5, 0.25, 0.125, 0.0625, 0.03125, 0.015625, 0.0078125, etc.  As you can see, we have to take a binary fraction out to 7 places before we get less than 0.01 (base 10).


The Visual Basic code below will only output 20 bits, including the decimal point.  You can modify this yourself by changing the value assigned to intNumBits near the top of the listing.  The embedded comments in the code should be fairly explanatory, but if you have questions or comments, feel free to leave a comment to this post.

Private Sub Dec2Bin_Click()

'   Subroutine to convert floating point decimal values to floating point binary values.
'
'   Written by: Erik Oosterwal
'   Started on: October 26, 2005
'   Completed:  October 27, 2005

    Dim txtNumericBaseData, txtOutputValue As String
    Dim intX, intNumBits As Integer
    Dim dblDecimalValue, dblFractionValue, dblBinaryFraction As Double
        
        
    intNumBits = 20             ' The number of bits in the output (including the decimal point)
    txtNumericBaseData = "01"   ' Output digits can be either "0" or "1"
    dblBinaryFraction = 0.5     ' Binary fraction bits are powers of 0.5
    txtOutput.Text = ""         ' Clear the display
    txtOutputValue = ""         ' Clear the working output variable
    
    
    dblDecimalValue = Int(CDbl(txtInput.Text))                  ' Get the integer portion of the input
    dblFractionValue = CDbl(txtInput.Text) - dblDecimalValue    ' Get the fractional portion of the input
        
        
'   Figure out the integer portion of the input.
    While dblDecimalValue > 0
        intX = Int(((dblDecimalValue / 2) - Int(dblDecimalValue / 2)) * 2 + 1.5)
        txtOutputValue = Mid(txtNumericBaseData, intX, 1) + txtOutputValue
        dblDecimalValue = Int(dblDecimalValue / 2)
    Wend
    
    
    If txtOutputValue = "" Then txtOutputValue = "0"    ' If there was no whole number, set it to "0"
    txtOutputValue = txtOutputValue + "."               '   then add a decimal point
    
    
'   Figure out the fractional portion of the input.
    While Len(txtOutputValue) < intNumBits And dblFractionValue > 0     ' As long as we're not exceeding the
                                                                        ' allowed number of bits in the output
                                                                        ' and there's still part of the input
                                                                        ' value to be converted...
        If dblFractionValue >= dblBinaryFraction Then                   ' If the input number is larger than the fraction bit,
            txtOutputValue = txtOutputValue + "1"                       '   add a "1" to the output and
            dblFractionValue = dblFractionValue - dblBinaryFraction     '   reduce the input number by the fraction bit's value.
        Else                                                            ' Otherwise...
            txtOutputValue = txtOutputValue + "0"                       '   just tag on a "0" to the end of the output.
        End If
        dblBinaryFraction = dblBinaryFraction / 2#                      ' The fraction bit must be cut in half.
    Wend
    
    txtOutput.Text = txtOutputValue                     ' Send the output value to the display.

End Sub

For a more generalized routine that can convert integer values between any two numeric bases, see the Numeric Base Conversion article from the main Computer Science 101 page.


You can also download a zip file that contains the listing given above as well as an executable file that demonstrates this routine.

Convert Decimal Values to Roman Numerals - Algorithm 1

Roman numerals follow a fairly strict rule in sequence in order to reduce ambiguity in numbers. To create Roman numerals we must first define which letters represent which values, and what exceptions there are to the basic rule.

First, the following letters represent the associated values:

I = 1

V = 5

X = 10

L = 50

C = 100

D = 500

M = 1000


The basic rule states that numerals are read from left to right, larger valued letters precede smaller valued letters, and multiple letters in a row represent multiples of that value. For instance:


I = 1
II = 2
III = 3
VIII = 8
CVIII = 108
CCVIII = 208
DCCVIII = 708
MDCCVIII = 1708


The single exception to the basic rule is that if a larger value letter is preceded by a single smaller value letter, then the combination represents the value of the larger value letter minus the value of the smaller value letter. This exception only holds true for the values 4, 9, 40, 90, 400, and 900, which are written as IV, IX, XL, XC, CD, and CM respectively.

A seldom used convention of Roman numerals is that you can create values larger values by overscoring letters to represent the letter's normal value multiplied by 1000:


_
V = 5000
_
X = 10,000
_
L = 50,000
_
C = 100,000
_
D = 500,000
_
M = 1,000,000



We won't bother with the larger values in this routine and limit our numbers to values between 1 and 3999.



DECIMAL to ROMAN Algorithm 1

The following pseudo code should provide enough information to implement the algorithm in your language of choice:

function roman(InputValue) as string

dim InputValue as integer  ' Declare Variables
dim RomanValue as string

if (InputValue > 3999) OR (InputValue < 1)
 roman = "N/A"
 return
endif

RomanValue = ""

While InputValue > 999 (
  RomanValue = RomanValue + "M" ' Concatenate the letters to the right side
  InputValue = InputValue - 1000 ' Reduce the amount left in InputValue
)

If InputValue > 899 (
  RomanValue = RomanValue + "CM" ' Concatenate letters to the right side
  InputValue = InputValue - 900
)

If InputValue > 499 (
  RomanValue = RomanValue + "D"
  InputValue = InputValue - 500
)

If InputValue > 399 (
  RomanValue = RomanValue + "CD"
  InputValue = InputValue - 400
)

While InputValue > 99 (
  RomanValue = RomanValue + "C"
  InputValue = InputValue - 100
)

If InputValue > 89 (
  RomanValue = RomanValue + "XC"
  InputValue = InputValue - 90
)

If InputValue > 49 (
  RomanValue = RomanValue + "L"
  InputValue = InputValue - 50
)

If InputValue > 39 (
  RomanValue = RomanValue + "XL"
  InputValue = InputValue - 40
)

While InputValue > 9 (
  RomanValue = RomanValue + "X"
  InputValue = InputValue - 10
)

If InputValue > 8 (
  RomanValue = RomanValue + "IX"
  InputValue = InputValue - 9
)

If InputValue > 4 (
  RomanValue = RomanValue + "V"
  InputValue = InputValue - 5
)

If InputValue > 3 (
  RomanValue = RomanValue + "IV"
  InputValue = InputValue - 4
)

While InputValue > 0 (
  RomanValue = RomanValue + "I"
  InputValue = InputValue - 1
)

roman = RomanValue

return

This is not a particularly efficient algorithm. In later articles additional algorithms will be discussed that show better ways to convert from Decimal Values to Roman Numerals and from Roman Numerals back to Decimal Values.