LMC - Decimal to binary with rest

Question

I am working on a challenge to write a program for the Little Man Computer:

This program should take a decimal number as input and output the binary equivalent. It should repeatedly divide the input by 2, and then output the remainders.

For example, if the input is 8, the machine should divide 8 by 2 and output 0. Then, it should divide 4 by 2 and output 0. Next, it should divide 2 by 2 and output 0. Finally, it should divide 1 by 2 and output 1.

Here is my code:

         INP
         STA NUM
         LDA 0
         STA REMAIN

LOOP     LDA NUM
         SUB TWO
         BRP CONTINUE
         BRA END

CONTINUE LDA REMAIN
         ADD ONE
         STA REMAIN
         BRA LOOP

END      LDA REMAIN
         OUT
         HLT

NUM      DAT
REMAIN   DAT
ONE      DAT 1
TWO      DAT 2

Problem

When I run this program with input 8 it just keeps on looping. When debugging I see that REMAIN is not initialised to 0 as I had expected, but to 901??. Then still I don't understand why this should cause an infinite loop, as I repeatedly subtract 2 and at a certain point this should lead to a negative number. Yet somehow this just never happens.

What is my mistake?

Answer 1

Here are some basic tips regarding the code you've posted.

• LDA 0 doesn't do what you want: it treats 0 as an address and so loads from memory location 0 (which actually holds code rather than data; here it holds the first instruction INP which has value 901, so def not 0.).  You need to use a datum with value 0, just like the SUB TWO — so do LDA ZERO, and define ZERO DAT 0 along with your other constants.

• To subtract from NUM with permanence, you need a load-subtract-store sequence.  Since you're not storing back to NUM, NUM will never change — so put a STA NUM after the load & subtract, as you're doing with REMAIN

  • (Btw the approach of counting the number of times a divisor can be subtracted from a dividend (before the updating dividend goes <= 0) computes a quotient — a remainder is what's left in a updated dividend when the divisor can no longer be subtracted from that updated dividend).

Further,

• Learn how to use the debugger, and observe when something doesn't work like you expected it to.  You can ask questions about debugging, if they are sufficiently specific.  Single step and observe the effects of each line; if anything unexpected happens, that's what to start looking at.  Here, had you single stepped, you might have noticed that LDA 0 doesn't load 0 into the accumulator, but rather 901 — so only 3 instructions into the program we have something unexpected.

• When you ask a question here, try to ask a question in your own words and be specific about what part of your code is malfunctioning or what you don't understand.  Questions like Can you write this program are too generic here.  We're not about writing code for you, but helping you get past where you're stuck so you can continue your project.  In order for that to work well, you have to (a) try yourself, and (b) give us an indication of where you're stuck.

Answer 2

You have described an algorithm that will output a number in its binary representation, reversed(!). I will assume this is what you want to achieve.

There are several issues in your attempt:

• LDA 0 will load the value in mailbox 0, which is not what you want. Instead label a mailbox as ZERO and initialise it with value 0, then do LDA ZERO.

• REMAIN is a misleading name, because your code will not store the remainder there, but the quotient of the division by 2. The remainder is what remains in NUM after the repeated subtractions of 2. I would use the label QUOTIENT or HALF instead.

• Related: the final output of REMAIN does not output a remainder, but a quotient. As you want to output only 0 or 1, your output should depend on something like NUM, not on REMAIN.

• Your loop never updates NUM, so the result of the subtraction with 2 is lost, and the next iteration of the loop will start again with the original value of NUM and do exactly the same thing again, leading to an infinite loop when NUM is 2 or more. There should be a STA NUM at the CONTINUE label.

• No distinction is made between the case where NUM is odd or even. The only event that is captured is when the subtraction leads to a negative overflow, but then you don't know whether to output a 0 or 1. You should add a BRZ instruction to detect the case where NUM is zero, so that you know that an output of 0 is needed. The other case, when to output 1, will then be identified by the negative overflow.

• Your program only foresees to output once, yet you want to potentially output multiple numbers (all 0 or 1). So there should be another loop for this, which takes the quotient (half of the value of original NUM) and uses it as NUM to repeat the whole process. This should continue until the quotient is zero.

Here is your code with all those remarks taken into account:

#input: 41
          INP

CALCULATE STA NUM
          LDA ZERO
          STA HALF # This is not the remainder, but quotient

LOOP      LDA NUM
          BRZ OUTPUT # Detect when to output a zero
          SUB TWO
          BRP CONTINUE

OUTPUT    LDA NUM # output the remainder
          OUT
          LDA HALF # now work with quotient
          BRZ END
          BRA CALCULATE # ... and repeat a division by 2

CONTINUE  STA NUM # Save before continuing
          LDA HALF
          ADD ONE
          STA HALF
          BRA LOOP

END       HLT

NUM       DAT
HALF      DAT
ZERO      DAT 0
ONE       DAT 1
TWO       DAT 2


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

You can run it here. It will default to input 41 (as example) for which the output will be:

1 0 0 1 0 1

Again this is reversed binary, so 0b101001, i.e. 32 + 8 + 1

On a final note, this is not the most efficient algorithm, as the number of subtractions will be /2 + /4 + /8 + ... = O(). This could be done in O(log) time complexity if you would work with subtractions of powers of 2, instead of always 2. This will come at the cost of a bit more complex program.