How to produce dividend and remainder in a little man computer program?

Question

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.

Answer 1

There are several issues with your program:

• OUT does not take an argument. It should not be OUT Q, but just OUT. 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 at END. 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 using BRZ there, you should build your loop-condition logic using BRP.
• 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 a DAT 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>

Answer 2

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.