Writing a program to convert multiple Roman numerals to a base-10 decimal number

Question

I have written a Little Man Computer program to solve the following code challenge. But it doesn't produce the expected results.

The code challenge

The program should convert a given Little Man number into a number using the base-10 number system.

A Little Man number is encoded by 6 inputs, inspired by the Roman numeral system:

• Input #1 represents a coefficient for the number 500, like how many D you would have in a roman numeral
• Input #2 represents a coefficient for the number 100, like how many C you would have in a roman numeral
• Input #3 represents a coefficient for the number 50, like how many L you would have in a roman numeral
• Input #4 represents a coefficient for the number 10, like how many X you would have in a roman numeral
• Input #5 represents a coefficient for the number 5, like how many V you would have in a roman numeral
• Input #6 represents a coefficient for the number 1, like how many I you would have in a roman numeral

The program should calculate the sum of these and output it.

Examples

If we give an input like 1,1,1,1,1,1 the output should be 666, as that is D+C+L+X+V+I with Roman numerals. Similarly if I give an input 0,0,0,0,0,1 the output should be 1.

If the user provides the inputs 0, 0, 0, 1, 2, 2, then this will be the equivalent of X+V+V+I+I (=0+0+0+10+25+21) = 22.

The program should only be able to calculate a natural number up to and including 999. If the user enters a Little Man numeral that exceeds this, the output is to be 999. 

My code

This is my attempt at solving this challenge:

| Input section

IN       | Read values for D, C, L, X, V, and I
STO D    | Store D
IN
STO C    | Store C
IN
STO L    | Store L
IN
STO X    | Store X
IN
STO V    | Store V
IN
STO I    | Store I

| Calculate the base-10 number

LDA D
BRZ SKIP_HUNDRED_THOUSANDS | If D is zero, skip calculation
ADD FIVEHUNDRED | Add the value of 500 times the hundred thousands place
STO RESULT | Store the result in memory location RESULT

SKIP_HUNDRED_THOUSANDS: LDA C
BRZ SKIP_TEN_THOUSANDS | If C is zero, skip calculation
ADD HUNDRED | Add the value of 100 times the ten thousands place
STO TEMP | Store the intermediate result in TEMP
LDA RESULT | Load the accumulated result
ADD TEMP | Add the intermediate result
STO RESULT | Store the updated result

SKIP_TEN_THOUSANDS: LDA L
BRZ SKIP_THOUSANDS | If L is zero, skip calculation
ADD FIFTY | Add the value of 50 times the thousands place
STO TEMP | Store the intermediate result in TEMP
LDA RESULT | Load the accumulated result
ADD TEMP | Add the intermediate result
STO RESULT | Store the updated result

SKIP_THOUSANDS: LDA X
BRZ SKIP_HUNDREDS | If X is zero, skip calculation
ADD TEN | Add the value of 10 times the hundreds place
STO TEMP | Store the intermediate result in TEMP
LDA RESULT | Load the accumulated result
ADD TEMP | Add the intermediate result
STO RESULT | Store the updated result

SKIP_HUNDREDS: LDA V
BRZ SKIP_TENS | If V is zero, skip calculation
ADD FIVE | Add the value of 5 times the tens place
STO TEMP | Store the intermediate result in TEMP
LDA RESULT | Load the accumulated result
ADD TEMP | Add the intermediate result
STO RESULT | Store the updated result

SKIP_TENS: LDA I
BRP EXCEEDS_LIMIT | If I is positive, jump to EXCEEDS_LIMIT

| Output section
LDA RESULT | Load the accumulated result
OUT | Output the result
HLT | Halt the program

| Handle case where input exceeds limit
EXCEEDS_LIMIT: LDA LIMIT_OUTPUT
OUT
HLT

| Data section
D: DAT 000
C: DAT 000
L: DAT 000
X: DAT 000
V: DAT 000
I: DAT 000
RESULT: DAT 000
TEMP: DAT 000
FIVEHUNDRED: DAT 500
HUNDRED: DAT 100
LIMIT_OUTPUT: DAT 999
FIFTY: DAT 050
TEN: DAT 010
FIVE: DAT 005

But this code is not giving the proper output, not for any of the above given examples.

What am I doing wrong here?

Answer 1

There are several issues in your attempt:

LDA D
BRZ SKIP_HUNDRED_THOUSANDS | If D is zero, skip calculation
ADD FIVEHUNDRED | Add the value of 500 times the hundred thousands place

The last instruction adds 500 to the accumulator, not to the result. At that moment the accumulator has the value of D, and so now you have D+500. When D is 1, this means you now have 501, which is not what you want.

A similar thing happens with the other inputs, so also C+100 is stored in TEMP, but actually you want to store C * 100 in TEMP (a product, not a sum). To multiply in LMC you need to create a loop and in this case add 100 repeatedly (C times).

Another issue occurs here:

LDA I
BRP EXCEEDS_LIMIT | If I is positive, jump to EXCEEDS_LIMIT

There is no reason why a positive I would mean the result exceeds the limit. Moreover, BRP will check if the last subtraction resulted in overflow (on some LMC implementations also when the last addition resulted in overflow).

Secondly, there is no part of your code that attempts to add I to the result.

Solution

As discussed above, you need to implement loops to calculate a product (to calculate things like C * 100, L * 50, ...). There are two exceptions:

• D should be 0 or 1, because if it is 2 or more, the result exceeds 999. So you don't really need a loop here and can just distinguish the three cases:

  • D is 0: nothing to do to the result
  • D is 1: account for 500
  • any other value: output 999

• I represents unit values, so you can just add the value of I to the result.

There is another behaviour to take into account: there is no strict specification for LMC what should happen if an addition leads to overflow. Wikipedia on LMC says about the ADD instruction:

the actions of the accumulator (calculator) are not defined for add instructions that cause sums larger than 3 digits. Similarly to SUBTRACT, one could set the negative flag on overflow.

So it could be that a particular LMC emulator will set the negative flag when ADD leads to overflow, but it is not guaranteed that this will happen on all compliant LMC emulators. We should thus not rely on such behavior. However, it is guaranteed that when SUB leads to overflow that the negative flag will be set. So to detect overflow, we should perform subtractions, not additions. This we can do by starting with the value 999 in the result, and then subtracting values from it. At the end we should not forget to invert that result before outputing it.

Implementation

Here is a runnable implemenation:

#input:1 1 1 1 1 1
              IN  | Read values for D, C, L, X, V, and I
              STO D
              IN 
              STO C
              IN 
              STO L
              IN 
              STO X
              IN 
              STO V
              IN 
              STO I

| Addition does not guarantee overflow detection (over 999), so perform subtractions 
| instead of additions, starting at 999, so we can detect overflow below 0.
              LDA LIMIT_OUTPUT
              STO RESULT

LOOP_D        LDA D
              BRZ PROCESS_C
              SUB TWO | D should be at most 1, as 2 results in overflow
              BRP EXCEEDS_LIMIT
              LDA RESULT
              SUB FIVEHUNDRED
              STO RESULT

PROCESS_C     LDA C
              SUB ONE
              BRP CONTINUE_C
              BR  PROCESS_L
CONTINUE_C    STO C
              LDA RESULT
              SUB HUNDRED
              STO RESULT
              BRP PROCESS_C
              BR  EXCEEDS_LIMIT

PROCESS_L     LDA L
              SUB ONE
              BRP CONTINUE_L
              BR  PROCESS_X
CONTINUE_L    STO L
              LDA RESULT
              SUB FIFTY
              STO RESULT
              BRP PROCESS_L
              BR  EXCEEDS_LIMIT

PROCESS_X     LDA X
              SUB ONE
              BRP CONTINUE_X
              BR  PROCESS_V
CONTINUE_X    STO X
              LDA RESULT
              SUB TEN
              STO RESULT
              BRP PROCESS_X
              BR  EXCEEDS_LIMIT

PROCESS_V     LDA V
              SUB ONE
              BRP CONTINUE_V
              BR  PROCESS_I
CONTINUE_V    STO V
              LDA RESULT
              SUB FIVE
              STO RESULT
              BRP PROCESS_V
              BR  EXCEEDS_LIMIT

PROCESS_I     LDA RESULT
              SUB I
              STO RESULT
              BRP OUTPUT

| Output section: 
| Handle case where input exceeds limit
EXCEEDS_LIMIT LDA LIMIT_OUTPUT
              OUT
              HLT
| Normal case: invert RESULT as we subtracted from 999
OUTPUT        LDA LIMIT_OUTPUT
              SUB RESULT
              OUT
              HLT


| Data section: variables
D             DAT 0
C             DAT 0
L             DAT 0
X             DAT 0
V             DAT 0
I             DAT 0
RESULT        DAT 0
| Data section: constants
LIMIT_OUTPUT  DAT 999
FIVEHUNDRED   DAT 500
HUNDRED       DAT 100
FIFTY         DAT 50
TEN           DAT 10
FIVE          DAT 5
TWO           DAT 2
ONE           DAT 1


<script src="https://cdn.jsdelivr.net/gh/trincot/[email protected]/lmc.js"></script>