How to loop and encode as binary?

Question

I am trying to get a program running in the LMC that converts any numerical to binary.

Normally I would just use the divide method, but I cannot do that since the Little Man Computer does not allow for divide or multiplication. The farthest I've gotten in this is only a simple INP. At this stage I do not know how to start loops in it, or how to even begin.

How can I start loops? And how do I stop them? I would somehow need a repeating loop that subtracts a value until it either reaches a 1 or 0. That will achieve my goal as I can just output it then.

For example: I enter 33 and it gives a 100 001 in the output.

I'm a total beginner. I just picked it up today, so keeping it simple would be greatly appreciated.

Answer 1

You write that for 33 the output should be 100 001. This may not work (depending on the LMC simulator), as the second value could be output without the prepadded zeroes, and so it would show 100 1. This can be confusing as it looks a lot like what you would expect for input 9.

I would suggest outputting each binary digit as a separate number: that way you ensure that all digits are visible in the output.

An algorithm to encode an input n like that, could be as follows:

1. Compare n with 512. If it is not less:

   a. Output 1, and subtract 512 from n, otherwise:

   b. Output 0

2. Double the value of n, i.e. add n to itself

3. Repeat the above 9 more times. Decrement a counter that starts with 10 and repeat as long as it does not set the negative flag.

How to loop

So you "start" a loop in a static way: set the initial value of a counter in a DAT instruction. In the above algorithm we want the counter to start at 10:

COUNTER DAT 10

Then when you need to loop, decrement the counter:

LDA COUNTER
SUB ONE
STA COUNTER

And (like many LMC programs), you need a constant ONE for this:

ONE DAT 1

Finally, to know whether the counter did not go below 0, you can check the "negative" flag. This is a flag that can be set by SUB, when there is a negative overflow (remember that the LMC cannot really store negative values, so you only have the flag as indication). The BRP instruction (branch when positive) will use that flag to decide whether to jump or not:

BRP LOOP

LOOP should be the label for where the code of your loop started.

Implementation

Note that in this practical case, it isn't useful to execute this loop more than 10 times, since the input in LMC cannot be more than 999, which in binary takes 10 digits.

Here is the implementation of the above described algorithm, with also a precaution that the counter will start at its initial value even when the program counter is reset after a first execution:

#input:13
         INP
         STA NUM
         LDA NINE
LOOP     STA COUNTER
         LDA NUM
COMPARE  SUB POW_9
         BRP BIT1
BIT0     LDA ZERO
         OUT
         BRA DOUBLE
BIT1     STA NUM  ; Reduce number with 512
         LDA ONE
         OUT
DOUBLE   LDA NUM
         ADD NUM
         STA NUM
         LDA COUNTER
         SUB ONE
         BRP LOOP
ZERO     HLT
POW_9    DAT 512
ONE      DAT   1
NINE     DAT   9
NUM      DAT
COUNTER  DAT

<script src="https://cdn.jsdelivr.net/gh/trincot/lmc@v0.7/lmc.js"></script>

Alternative

There are several other ways to accomplish this task. For instance, we can hard-code the powers of 2 that we need for 10 binary digits: 1, 2, 4, ..., 512.

Then compare the input value with the greatest of those (with 2⁹ = 512). If it is not less, then output a 1 bit, otherwise output 0. If 1, then subtract that power of 2 from the input number. In both cases, switch to the previous power of 2 (2⁸) and repeat this process. Repeat this until you've done the job for 2⁰.

You could try to implement this without a loop, but you'll have 10 times the same code, with just a different power of 2. This may even be a challenge to fit in the LMC's memory of 100 "mailboxes" (It would work however if you limited the input to like 64, so you would only need 6 binary digits).

To implement this with a loop (less code), you can use a technique of indirect addressing. In LMC there is no instruction for indirect addressing, but with self-modifying code it is possible.

Suppose you have the list of powers implemented as follows:

POW_9   DAT 512
POW_8   DAT 256
; ... etc
POW_0   DAT 1

Then you would do a comparison of the accumulator with POW_9 by:

COMPARE SUB POW_9

The label allows us to store a different instruction there, so that the next time it is executed it actually executes this:

COMPARE SUB POW_8

This is possible with the following manipulation:

LDA COMPARE
ADD ONE
STA COMPARE

This is a bit tricky because code is treated as data, and this modifies the code. Notice how changing SUB POW_9 is actually working as if you reference an element in an array, and increase the index in that array.

You need to have a stop-condition so that you don't make the code reference a power of 2 that is not in your DAT list. For that you could compare the modified code with a fixed piece of code (also a SUB, but which is never executed) that references the lowest power of 2.

Here is an implementation of this idea:

#input:13
         INP
         STA NUM
         LDA FIRST
LOOP     STA COMPARE ; self-modifying code!
         SUB LAST    ; Compare with "SUB ZERO"
         BRP ZERO  
         LDA NUM
COMPARE  SUB POW_9 ; Indirect addressing
         BRP BIT1
BIT0     LDA ZERO
         OUT
         BRA NEXT
BIT1     STA NUM  ; Reduce number with power
         LDA ONE
         OUT
NEXT     LDA COMPARE ; Change power of 2
         ADD ONE
         BRA LOOP
FIRST    SUB POW_9  ; Never executed
LAST     SUB ZERO   ; Never executed
POW_9    DAT 512
POW_8    DAT 256
POW_7    DAT 128
POW_6    DAT  64
POW_5    DAT  32
POW_4    DAT  16
POW_3    DAT   8
POW_2    DAT   4
POW_1    DAT   2
ONE      DAT   1
ZERO     HLT
NUM      DAT

<script src="https://cdn.jsdelivr.net/gh/trincot/lmc@v0.7/lmc.js"></script>