C++ converting base 10 to Roman numerals

  • Thread starter Thread starter Math Is Hard
  • Start date Start date
  • Tags Tags
    Base C++
AI Thread Summary
The discussion centers on converting base 10 numbers to Roman numerals using C++. The original poster struggles with implementing a loop to handle the conversion efficiently without using arrays, as they are not yet familiar with that concept. Suggestions include using functions to encapsulate repeated logic and considering a while loop for subtraction instead of division for better efficiency. Participants also discuss the importance of maintaining the correct order of Roman numeral symbols during conversion and share various coding approaches, emphasizing clarity and elegance in the code. Ultimately, the conversation highlights the challenges and strategies involved in programming this conversion task effectively.
Math Is Hard
Staff Emeritus
Science Advisor
Gold Member
Messages
4,650
Reaction score
39
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
103 , (103)/2 , 102 , (102)/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:

Code: 
# 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;
}
 
Physics news on Phys.org
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.
 
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?
 
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...
 
ok, I'll think on that. That should make things a little bit nicer (and shorter!). Thanks!
 
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;
}
 
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
 
Last edited:
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.
 
No, the way she did it is more concise than that would be.
 
  • #10
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.
 
  • #11
Bartholomew said:
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?
 
  • #12
Well, probably my CPU does know the difference. But I was talking more about shorter source code.
 
  • #13
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. :biggrin:

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.
 
  • #14
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 %.
 
  • #15
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.
 
  • #16
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.
 
  • #17
It is interesting. And now it's even more complicated. So which system of "Roman" numerals are you supposed to convert to?
 
  • #18
"...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".
 
  • #19
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
 
Last edited by a moderator:
  • #20
Yeah, that's what my program does. And MCMXCIX for 1999.
 
  • #21
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! :smile:
 
  • #22
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.
 
Last edited:
  • #23
plover said:
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.
 
  • #24
I would just do it like this:

Code: 
It is in white in case somebody does not want the answer spoiled...
# 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;
	}
}
 
  • #25
GADS, that is inelegent... put it works..
 
  • #26
I still like the old-fashioned way:
Code: 
//  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;
}
 
  • #27
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).
 
  • #28
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!
 
  • #29
"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.
 
  • #30
Bartholomew said:
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. :smile: :smile: :smile:


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.
 
  • #31
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:

Code: 
# 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.
 
Last edited:
  • #32
It would be even more elegant if it actually worked. :wink:

I usually prefer code that's straightforward & easy to read, but if you want tricky, here's a "user-friendly" one that does work:
Code: 
#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;
}
 
  • #33
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.
 
  • #34
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.
 
  • #35
There's still something wrong, for example:
2949
MMDCDXLVIV
 
  • #36
What's "normal"? And waddaya mean longer? You're not going to charge me for the "amenities", are you?
:smile:
 
  • #37
MMDCDXLVIV is correct for 2949.

Point is, my algorithm is inherently simpler than yours.
 
  • #38
2949=MMCMXLIX
 
  • #39
Bartholomew said:
Point is, my algorithm is inherently simpler than yours.

uh oh. them sounds like fightin' words..
 
  • #40
Bartholomew said:
Point is, my algorithm is inherently simpler than yours.

But I thought now we're going for tricky. :cry: :cry: :cry:
 
  • #41
According to that page on roman numerals, IX is incorrect... you can't have a I and then an X, it skips the V, the same reason IMM is incorrect.
 
  • #42
Math Is Hard said:
uh oh. them sounds like fightin' words..
See what you started! o:) o:)
 
  • #43
gnome said:
See what you started! o:) o:)
I know. Mea culpa.
If it's any consolation I think I failed spectacularly on the C++ midterm today. Guess what was on the test - converting to Roman f'ing numerals! :cry: I couldn't remember anything. I was like a deer in the headlights I was so scared.
 
  • #44
I didn't study that page, but I'm sure that 9 is generally written IX and not VIV.
 
  • #45
On the other hand, it's a lot more fun than studying for an exam on computabilty, complexity, etc. -- which is what I should be doing. :devil: :devil:

I'll check back later to see what Bartholomew comes up with.
 
  • #46
My algorithm is the best. Given an integer, look up its string representation in a table of strings. :smile:
 
  • #47
Well, as I said, I don't have a c++ compiler. So rather than translate this into C++ and hope I didn't make any syntax errors in doing so, I'll just post it in Java, which I wrote it in. (No user input here since that takes several lines in Java)
Code: 
class RomanNumeral{
	public static void main (String argv[])
	{
		int num, i, ii;
		int cD[] = {1000, 500, 100, 50, 10, 5, 1};
		int c[] = new int[7];
		String cs = "MMMDDDCCCLLLXXXVVVIII";
		num = 2949;
		for(i=-1;i<6;c[++i]=num/cD[i],num%=cD[i]);
		for(i=0;i<7;i++)
			System.out.print(c[i]!=4||i==0?cs.substring(i*3,i*3+c[i]):""+
					cs.charAt(i*3)+cs.charAt(i*3-1));
	}
}
 
  • #48
Bartholomew said:
I'll just post it in Java
Oh no! Now everyone's posting condensed code samples in random languages – this thread is turning into the Obfuscated Roman Numeral Programming Competition... :-p

In Python (this more-or-less does what I outlined earlier (rather inefficiently :wink:); I think it's also a version of Hurkyl's method):
Code: 
from sys import stdout
r = 'IVXLCDM'
print 'Decimal to Roman numeral conversions'
print 'Enter an integer 1-9999, press return or enter a non-integer to exit'
try:
    while True:
        n = int(raw_input('Your number? '))
        while (n<1) or (n>9999): n = int(raw_input('Bad number!\nYour number? '))
        if n > 999: stdout.write('M'*(n/1000))
        n = str(n % 1000)
        for (c1,c5,c10),d in [(r[i:i+3], int(n[-(i/2+1)])) for i in xrange((2*len(n)-2),-1,-2)]:
            stdout.write(['', c1, c1*2, c1*3, c1+c5, c5, c5+c1, c5+c1*2, c5+c1*3, c1+c10][d])
        stdout.write('\n')
except ValueError:
    print 'Bye!'
Batholomew said:
According to that page on roman numerals, IX is incorrect... you can't have a I and then an X, it skips the V, the same reason IMM is incorrect.
From the page linked by Integral:
The subtracted number must be no less than a tenth of the value of the number it is subtracted from. So an X can be placed to the left of a C or an L but not to the left of an M or a D.
In other words, 90 = XC not LXL, and thus 9 = IX not VIV. Just look at the page of conversions at Integral's link.
 
  • #49
You (Bartholomew) have disappointed me. :frown: :frown:

It's a few characters shorter than mine (ignoring the user chit-chat), but it's still wrong. Yes, your algorithm is simpler, but only because the language that it recognizes is simpler and as a result it fails to handle 9, 90 and 900 correctly.

Why did you think that 9 = VIV and 90 is LCL?

The Wolfram page that MathIsHard posted
http://mathworld.wolfram.com/RomanNumerals.html
clearly indicates that 9=IX and and 90=XC.

If you look at page "9" (roman-numbered) of the preface of any textbook, or the production date of any 20th century movie you'll see ix and MCM...

Bartholomew said:
According to that page on roman numerals, IX is incorrect... you can't have a I and then an X, it skips the V, the same reason IMM is incorrect.
What page were you referring to?
 
  • #50
If you don't have a Java SDE, here's a _tentative_ translation into C++. Probably this doesn't work, but hopefully you'll be able to correct the error if that's the case. (it won't be a logic error, it does work in Java) I also refined the code slightly while translating, to shave off an additional few characters and further complicate that beautiful cout of mine :smile: .

Code: 
#include <iostream>
int main(){
	int num, i;
	int cD[] = {1000, 500, 100, 50, 10, 5, 1};
	int c[7];
	string cs = "IIIVVVXXXLLLCCCDDDMMM";
	cin >> num;
	for(i=-1;i<6;c[++i]=num/cD[i],num%=cD[i]);
	for(i=6;i>-1;i--)
		cout<<(c[6-i]!=4||i==6?cs.substr(i*3,c[6-i]):cs.substr(i*3+2,2));
	return 0;
}
 

Similar threads

C/C++ Errors trying to compile a simple code
Replies
22
Views
3K
Comp Sci Convert between base system in C on Linux
Replies
3
Views
1K
TikZ: Clebsch-Gordon Table Generator
Replies
3
Views
3K
C/C++ How Can I Convert Quicksort from Java to C++?
Replies
3
Views
2K
Storing a number as digits in a linked list
Replies
10
Views
2K
C: Recursive function into iterative
Replies
2
Views
1K
Comp Sci C++ Error Checking (Simple program)
Replies
3
Views
1K
C++ printing and positioning with loops
Replies
15
Views
12K
C/C++ Trying to write a program that converts integers to roman numerals in C++
Replies
7
Views
15K
1D Particle & Energy w/ F(x): Am I doing this right?
Replies
7
Views
1K

Hot Threads

Recent Insights

Back
Top