Your Ad Here

Saturday, February 16, 2008

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.

2 comments:

Anirvana said...

Thanks! This is really helpful.

Ankush Bindlish said...

static void Main(string[] args)
{
Dictionary lookup = new Dictionary();
lookup.Add("I",1);
lookup.Add("V",5);
lookup.Add("X",10);
lookup.Add( "L",50);
lookup.Add("C",100);
lookup.Add( "D",500);
lookup.Add("M",1000);

var symbols = new string[] { "I", "V", "X", "L", "C", "D", "M" };
int number = 3999;
var roman = "";
// rule
if(number > 4999)
{
throw new ArgumentException("Invalid number");
}
for(int symbol = symbols.Length-1;symbol >= 0; symbol--)
{
var currentWeight = lookup[symbols[symbol]];
if (number >= currentWeight)
{
if(number/currentWeight <= 3)
{
if ((number % currentWeight) / lookup[symbols[symbol - 1]] <= 3)
{
roman += repeat(symbols[symbol], number / currentWeight);
}
else
{
continue;
}
}
else
{
roman += repeat(symbols[symbol ], 1);
if (number > lookup[symbols[symbol + 1]])
{
roman += repeat(symbols[symbol + 2], 1);
}
else
{
roman += repeat(symbols[symbol + 1], 1);
}
}
number = number % currentWeight;
}
}

}
private static string repeat(string val,int count)
{
var result = "";
for (int i = 0; i < count; i++)
result += val;
return result;
}