I am trying to write a LMC program that takes two integer inputs, divides them, and produces the quotient and remainder. To start, I broke down the problem into 4 stages:
1.Divide num1 by num2 to get the quotient, q.
2.Multiply q and num2 to get the exact multiplied number, and store it in num2.
3.Subtract num2 from num1, and store the answer in rem.
4.Output q and rem.
Here is the code I wrote:
INP
STA NUM1
LDA NUM1
STA ORG
INP
STA NUM2
BRZ END
LDA 99
STA Q
LOOP LDA NUM1
BRZ END
LDA NUM1
SUB NUM2
STA NUM1
LDA Q
ADD ONE
STA Q
BRA LOOP
LDA Q
STA NUM3
LDA NUM2
SUB ONE
STA NUM2
LOOP LDA NUM2
BRZ END
LDA NUM3
ADD Q
STA NUM3
LDA NUM2
SUB ONE
STA NUM2
BRA LOOP
LOAD ORG
SUB NUM3
STA REM
END LDA Q
OUT Q
LDA REM
OUT REM
HLT
NUM1 DAT
NUM2 DAT
ORG DAT
Q DAT
ONE DAT 1
TOTAL DAT
NUM3 DAT
REM DAT
When I try and run the code in an LMC simulator, it does not produce a result, instead it continues calculating indefinitely. How can I make it work? Is there a better way to do this? Any help is greatly appreciated.
CodePudding user response:
Is there a better way to do this?
Your approach is logical, but probably overkill. Just doing the division alone, and stopping when you can no longer subtract the divisor from the dividend will produce both the quotient and the remainder together.
For example, if you want to divide 13 by 4, then subtract 4 from 13 yielding 9, then subtract 4 from 9 yielding 5, then subtract 4 from 5 yielding 1, and now we stop as 4 is greater than 1 (we cannot subtract without going negative). The quotient is the number of times we were able to subtract 4 (which was 3 times), and the remainder is what's left after stopping, here, 1.
How can I make it work?
As far as why your code does infinite loop, it is probably that you're only looking for division that is exact, by using BRZ
. You should consider using BRP
instead, which will allow for a non-zero remainder. You should single step in the LMC debugger to see why it doesn't stop when you'd like it to.
CodePudding user response:
There are several issues with your program:
OUT
does not take an argument. It should not beOUT Q
, but justOUT
. A good LMC simulator should complain about this.LOOP
is defined twice as a label. This is ambiguous. A good LMC simulator should complain about this.- The code immediately below
BRA LOOP
is unreachable until the instructions atEND
. It is dead code. - The loop can only be exited when
NUM1
becomes zero, but that might never happen. For instance if you divide 4 by 5, then the subtraction will give a negative overflow, and the accumulator will not be zero (actually it is not defined by the language which value it would then have). Instead of usingBRZ
there, you should build your loop-condition logic usingBRP
. - The initialisation of
Q
is taken from mailbox 99, but that assumes that your program does not occupy mailbox 99. This is true, but it is better to use a label for aDAT 0
. - Not a problem, but the third instruction (
LDA NUM1
) is not necessary, as the accumulator already has that value.
The algorithm that you want to implement is a bit longwinded. After you have subtracted the second number from the first and no more subtractions are possible, you will already have the remainder (if you do it right).
Your algorithm should also deal differently with a 0 divisor: in that case maybe output some predefined value to indicate that the quotient is undefined, like 999.
Here is how you could code that. This is a runnable snippet with some example input you can adapt:
#input: 19 5
LDA zero # initialise
STA quotient
INP
STA remainder
INP
STA divisor
BRZ error # division by 0 is undefined
loop LDA remainder
SUB divisor
BRP continue
end LDA quotient # output the results
OUT
LDA remainder
OUT
HLT
continue STA remainder
LDA quotient
ADD one
STA quotient
BRA loop
error LDA big # output 999 twice to indicate error
OUT
OUT
HLT
remainder DAT
divisor DAT
quotient DAT
zero DAT 0
one DAT 1
big DAT 999
<script src="https://cdn.jsdelivr.net/gh/trincot/[email protected]/lmc.js"></script>
<iframe name="sif1" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>