C++ converting base 10 to Roman numerals

[Math Is Hard]

Hi,
I just began working on a little program to convert base 10 number to Roman numerals. I couldn't figure out how to make a loop to count how many Ms, Ds, Cs etc. so I wrote it out the long way for now.
I can see a lot a repetition and an obvious pattern in my divisors, since I am dividing by
10³ , (10³)/2 , 10² , (10²)/2 ,etc.
but I can't figure out a loop that will handle this properly. Any suggestions?
(note: I haven't written the logic for the last piece of it yet which will deal with the order of the numbers, for instance, converting VIIII to IX.)

Thanks for any advice on handling the loop. Here's what I did:

# include <iostream>

using namespace std;

//converts base 10 to romans

int main()
{
	int num;
	int quotient;
	int M = 0;
	int D = 0;
	int C = 0;
	int L = 0;
	int X = 0;
	int V = 0;
	int I = 0;

	cin >> num;

	quotient = num/1000;
	M = quotient;
	num = num % 1000;

	quotient = num/500;
	D = quotient;
	num = num % 500;
	
	quotient = num/100;
	C = quotient;
	num = num % 100;

	quotient = num/50;
	L = quotient;
	num = num % 50;
	
	quotient = num/10;
	X = quotient;
	num = num % 10;

	quotient = num/5;
	V = quotient;
	num = num % 5;
	
	I = num;


		for (int m = 0; m < M; m++)
			cout << "M";
		for (int d = 0; d < D; d++)
			cout << "D";
		for (int c = 0; c < C; c++)
			cout << "C";
		for (int l = 0; l < L; l++)
			cout << "L";
		for (int x = 0; x < X; x++)
			cout << "X";
		for (int v = 0; v < V; v++)
			cout << "V";
		for (int i = 0; i < I; i++)
			cout << "I";

	return 0;
}

 

[Hurkyl]

The trick is to make an auxilliary array of the constants you need.

int divisor[] = { 1000, 500, 100, 50, 10, 5, 1 };
char symbol[] = "MDCLXVI";

I'll give you a chance to take it from here.

 

[Math Is Hard]

Hey Hurkyl, thanks for your response.

sorry, I should have mentioned this in my first post: No arrays allowed yet.
Technically we're not supposed to know what an array is yet.
Think there might be another way?

 

[Hurkyl]

Well... you could write a function that contains the replicated logic, and then call the function a few times with the parameters. Or, you could put them into a file, and read them from the file instead of from an array...

 

[Math Is Hard]

ok, I'll think on that. That should make things a little bit nicer (and shorter!). Thanks!

 

[Bartholomew]

You can't have a loop because you have the separate variables M D C L X V I. There is no good way to access the M in the first iteration, the D in the second, etc. You could use 2 arrays, one to store the number of M's, D's, C's, etc. and the other to store the letters 'M,' 'D,' 'C,' etc., and that would let you do a loop. But unless you were specifically asked to use a loop, I don't think you should.

You can tighten the code by not initializing any of the M's, D's, etc. to 0 since they are assigned values later in the code before they are used.

Also, you can write

quotient = num/5;
V = quotient;
num = num % 5;

as

V = num/5;
num %= 5;

getting rid of the quotient variable.

If you do need a loop, it would go something like this (currentDivide set to 1000 to begin with):
for(i = 0; i < 7; i++)
{
(do something with your array of letters here)
if(i % 2 == 0)
currentDivide /= 2;
else
currentDivide /= 5;
}

 

[Bartholomew]

But I think you should focus on the second part of the problem. Your program would convert 499 into CCCCLXXXXVIIII, and there is not an easy way to go from there to the correct answer, ID, so you should convert it to ID as you go rather than afterwards.

Edit: nevermind, ID is not the standard representation for 499

 

[Integral]

Instead of dividing by 1000 do a loop that subtracts 1000, each loop add a M, check to see if you are below 1000, then start subtracting 500. etc. You will need to condsider the logic needed to get the order of the Roman Numeral symbols right.

I did this some years ago in quick basic, Sorry lost the code... Hum... I still have a collection 5.25 floppies I might be lucky and still have it somewhere.

 

[Bartholomew]

No, the way she did it is more concise than that would be.

 

[Math Is Hard]

OK, thanks! I am going to play around with some of those suggestions, but if I get stuck at least I have my long-winded version to use.

 

[Integral]

No, the way she did it is more concise than that would be.

Surely you jest! We are converting to Roman numerals aren't we?

Can you tell me exactly what the difference between subtraction and division is? Does your CPU know the difference?

 

[Bartholomew]

Well, probably my CPU does know the difference. But I was talking more about shorter source code.

 

[Integral]

Actually your CPU does division by successive subtractions.

I am not sure that the division algorithm is more efficient. Since you will have to do some form of a loop based on the result of the division to create the final answer. This way you do a while loop subtracting the appropriate amount and build the result as you go, you can even throw in the ordering logic. The subtraction saves machine cycles...LOL as if that is a concern for this problem.

I would recommend doing it the way that easiest to code. That comes down to what works for, and makes the most sense to, the programmer.

 

[Bartholomew]

I'm not familiar with the specifics of my computer's innards but I'm willing to bet that it has division instructions which are more efficient than successive subtraction. Long division by hand, for example, is quicker than repeated subtraction by hand.

Personally, I'm used to dividing and using %.

 

[gnome]

I think this involves too many special cases to have "elegant" code. You have to deal separately with thousands, nine-hundreds, five-hundreds, four-hundreds, hundreds, nineties, fifties, forties, tens, nine, five, four and one; Integral's way is best.

 

[Math Is Hard]

I'm trying to work out the rest of the Roman numeral formatting now to put the I before the V or the I before the X. I'm stumped on that so far but I think I'm just burning out now. Maybe if I sleep on it... :zzz: .. sometimes I'll have an idea in the morning.
I've been reading this page for help, if anyone's interested in Roman Numeral rules and trivia.

 

[gnome]

It is interesting. And now it's even more complicated. So which system of "Roman" numerals are you supposed to convert to?

 

[gnome]

"...now to put the I before the V or the I before the X..." or the X before the C (or L) or the C before the M (or D) and so on...

That's why Integral suggested building the string while whittling down the decimal number. Or, if you're not up to strings yet, just print each character or pair of characters in the same loop with the subtraction. In other words, if you have nine-hundred-something, subtract nine hundred, print "CM" and then continue processing the "something".

 

[Integral]

Ya'll got me wondering aobut correct form of Roman numerals, I had a pretty good sense of how it works but was not certian. I found http://www.wilkiecollins.demon.co.uk/roman/front.htm

check out the conversion calculator (I scored X/X on the little test!)

Also look at the 1999 question.

according to this page ID is not the best form of 499 it would be CDXCIX

 

[gnome]

Yeah, that's what my program does. And MCMXCIX for 1999.

 

[Integral]

I'll bet in Roman slang IMM was good enough for 1999. Also bet the old folks cursed the lazy kids that couldn't take the time to do it right!

 

[plover]

It seems to me that there's no need to determine the presence of the 5-ish characters (V, L, D) separately from the 1-ish characters (I, X, C). A function could be created that takes a decimal digit, and the appropriate characters for 1x, 5x, and 10x of that digit (the 10x being necessary if the digit is 9); the function would test the digit and output the characters in the needed format. Each digit in a decimal representation actually provides an independent contribution to the final Roman numeral representation.

 

[Integral]

It seems to me that there's no need to determine the presence of the 5-ish characters (V, L, D) separately from the 1-ish characters (I, X, C). A function could be created that takes a decimal digit, and the appropriate characters for 1x, 5x, and 10x of that digit (the 10x being necessary if the digit is 9); the function would test the digit and output the characters in the needed format. Each digit in a decimal representation actually provides an independent contribution to the final Roman numeral representation.

Yeah, this sounds like a good idea. One way to do it would be to grab the digit, use that as a index into an array that contains the correct pattern for that digit. Pretty simple.

Is C smart enough to give it a pattern and symbols then replicate the pattern with the given symbols? Since the pattern for 9 is the same whether it is 900, 90, or 9, just uses different symbols. Humm... not sure how to designate the patterns.. Sorry just thinking out loud.

 

[gerben]

I would just do it like this:

It is in white in case somebody does not want the answer spoiled...
[COLOR=black]# include <iostream>

using namespace std;

//converts base 10 to romans

void main()
{
	int num, i;

	cin >> num;

        for (i = 0; i < num/1000; i++)
		cout << "M";

	num = num % 1000;
	switch (num/100)
	{
		case 9:
			cout << "CM";
			break;
		case 8:
			cout << "DCCC";
			break;
		case 7:
			cout << "DCC";
			break;
		case 6:
			cout << "DC";
			break;
		case 5:
			cout << "D";
			break;
		case 4:
			cout << "CD";
			break;
		case 3:
			cout << "CCC";
			break;
		case 2:
			cout << "CC";
			break;
		case 1:
			cout << "C";
			break;
	}

 	num = num % 100;
	switch (num/10)
	{
		case 9:
			cout << "XC";
			break;
		case 8:
			cout << "LXXX";
			break;
		case 7:
			cout << "LXX";
			break;
		case 6:
			cout << "LX";
			break;
		case 5:
			cout << "L";
			break;
		case 4:
			cout << "XL";
			break;
		case 3:
			cout << "XXX";
			break;
		case 2:
			cout << "XX";
			break;
		case 1:
			cout << "X";
			break;
	}

 	num = num % 10;
	switch (num)
	{
		case 9:
			cout << "IX";
			break;
		case 8:
			cout << "VIII";
			break;
		case 7:
			cout << "VII";
			break;
		case 6:
			cout << "VI";
			break;
		case 5:
			cout << "V";
			break;
		case 4:
			cout << "IV";
			break;
		case 3:
			cout << "III";
			break;
		case 2:
			cout << "II";
			break;
		case 1:
			cout << "I";
			break;
	}
}[/COLOR]

 

[Integral]

GADS, that is inelegent... put it works..

 

[gnome]

I still like the old-fashioned way:

[COLOR=black]//  dec2rom.cpp
//	to run enter "dec2rom" followed by the number to be converted
//	>dec2rom 1967 <enter>
//	gives:
//	Decimal value: 1949
//	Roman equivalent: MCMXLIX


#include <iostream>
#include <stdlib.h>
#include <string>

int main(int argc, char *argv[]) {
    int dec = atoi(argv[1]);
    string rom;
    cout << "Decimal value: " << argv[1] << endl << endl;

    while(dec>=1000){
        dec -= 1000;
        rom = rom + "M";
    }
    if (dec>=900){
        dec-=900;
        rom = rom + "CM";
    }
    if(dec>=500){
        dec -= 500;
        rom = rom + "D";
    }
    if (dec>=400){
        dec -= 400;
        rom = rom + "CD";
    }
    while(dec>=100){
        dec = dec-100;
        rom = rom + "C";
    }
    if(dec>=90){
        dec -= 90;
        rom = rom + "XC";
    }
    if(dec>=50){
        dec -= 50;
        rom = rom + "L";
    }
    if(dec>=40){
        dec -= 40;
        rom = rom + "XL";
    }
    while(dec>=10){
        dec -= 10;
        rom = rom + "X";
    }
    if(dec == 9){
        rom = rom + "IX";
    }
    else{
        if(dec >= 5){
            dec -= 5;
            rom = rom + "V";
            }
        if(dec == 4){
            rom = rom + "IV";
        }
        else{
            while(dec > 0){
                dec -= 1;
                rom = rom + "I";
            }
        }
    }
    cout << "Roman equivalent: " << rom;
    cout << endl << endl;
}[/COLOR]

 

[Bartholomew]

There is a much more elegant way to do it. After you go through it the way MathIsHard did, you look at each of the "1-ish" characters (to use Plover's words), starting from the smallest, I, and going to the largest. If any of them contains the value 4, you replace it with a -1 and add 1 to the next-largest "5-ish" character. When you print, you check to see if the character you're about to print is followed by a -1. If it is, you print that next character (the one that contains -1) before you print the character you're about to print (so the -1 acts as a flag for the use of subtraction on the next-largest letter).

 

[Math Is Hard]

Apparently there are quite a few ways to skin this cat! I appreciate everyone's ideas on this. I am still tinkering with it to see what else I can come up with.
Thanks!

 

[DaveC426913]

"I'm not familiar with the specifics of my computer's innards but I'm willing to bet that it has division instructions which are more efficient than successive subtraction. Long division by hand, for example, is quicker than repeated subtraction by hand."

Don't be so sure. The guys at Sun Systems thought exactly the same thing. They assumed less vocabulary in their chip's instructions would cause it to run slower, so they decided to see how much slower.

They reduced the instructions available to the chip to as low as possible, expecting it to crawl. Astonishingly, it was actually faster. Thus was born the RISC (Reduced Instruction Set) chip.

A computer is good at nothing if not number-crunching fast. It's better at mindless number crunching than it is at interpreting and manipulating the various rules that govern, for example, long division. It may seem easy to your brain, but the steps in the long division algorithm are quite high-level in their functionality = lots computing cycles.

 

[gnome]

There is a much more elegant way to do it. After you go through it the way MathIsHard did, you look at each of the "1-ish" characters (to use Plover's words), starting from the smallest, I, and going to the largest. If any of them contains the value 4, you replace it with a -1 and add 1 to the next-largest "5-ish" character. When you print, you check to see if the character you're about to print is followed by a -1. If it is, you print that next character (the one that contains -1) before you print the character you're about to print (so the -1 acts as a flag for the use of subtraction on the next-largest letter).

So, to avoid exactly 6 subtractions (900, 400, 90, 40, 9, 4) and the immediate placement of the correct pairs of characters in the appropriate place in the string, you will first translate the decimal number into an incorrect string, then scan the string to count the number of occurrences of three particular characters, and replace those that occur in substrings of length 4 with a pair of characters, one of which is not a member of the output alphabet. Then, before printing, you scan the string yet again, looking for occurrences of that "extra" character, replace it with the correct character, and exchange the position of that character with the one preceding it, all in the name of elegance. :rofl: :rofl: :rofl:


That approach also requires the programmer to save, and to be able to manipulate, the string, in contrast with the more straightforward (and probably shorter) approach which can easily be modified to print the correct characters "on the fly" and eliminate saving the translated string altogether.

 

[Bartholomew]

Actually, my method does not use any strings until the actual printing, unlike yours.

And I don't scan it before printing; I simply do a check each time I print a 5-ish character.

As for how short the code is, it can be this short:

# include <iostream>
using namespace std;
int main()
{
	int num, i, ii;
	int currentDivide[7] = {1000, 500, 100, 50, 10, 5, 1};
	int count[7];
	char characters[7] = {'M', 'D', 'C', 'L', 'X', 'V', 'I'};
	cin >> num;
	for(i = 0; i < 7; i++){
		count[i] = num / currentDivide[i];
		num %= currentDivide[i];
	}
	for(i = 0; i < 7; i++)
		if(count[i] != 4 || i == 0)
			for(ii = 0; ii < count[i]; ii++)
				cout << characters[i];
		else
			cout << characters[i] << characters[i-1];
	return 0;
}

It's possible there's a bug in this code since I haven't tested it, but I think you'll agree it's fairly elegant. I could have used more lines of code to make the program more efficient in the print loop, but I decided against it.

 

[gnome]

It would be even more elegant if it actually worked.

I usually prefer code that's straightforward & easy to read, but if you want tricky, here's a "user-friendly" one that does work:

#include <iostream>
int main(){
    char l[] = "MDCLXVI";
    int r,d[]={9,5,4,1};
    cout << "Enter a positive integer to convert to Roman numerals:\n";
    cin >> r;
    do{
        int p=100;
        for(; r>=1000; r-=1000, cout << l[0]);
        for (int i=1; i<4; i++,p/=10){
            for(; r >= p*d[0]; r -= p*d[0], cout<<l[2*i]<<l[i*2-2]);
            for(; r >= p*d[1]; r -= p*d[1], cout<<l[2*i-1]);
            for(; r >= p*d[2]; r -= p*d[2], cout<<l[2*i]<<l[i*2-1]);
            for(; r >= p; r -= p, cout<<l[2*i]);
        }
        cout << "\n\nEnter the next number, or -1 to quit:\n";
        cin >> r;
    } while (r>=0);
    cout << "\n\nHave a nice day.";
    return 0;
}

 

[Bartholomew]

Oh, it doesn't work? You'll have to excuse me as I don't have a C++ compiler currently. I made some changes to it--tell me if they worked.

 

[Bartholomew]

Also, note that if you had written your code "normally," it would have been far longer than mine. As it is, it's only somewhat longer.

 

[gnome]

There's still something wrong, for example:
2949
MMDCDXLVIV