Implementing min of 3 numbers in Mic-1 code

Question

I have the following algorithm to find a minimum of three input numbers:

min(a,b,c):
   x := a
   if b < x then x := b
   if c < x then x := c
   return x
end min(a,b,c)

I'm trying to implement a Mic-1 micro code following the algorithms above:

OP1, OP2, OP3 = any 16 bit 2s complement value

OPRES: 0
      .LOC 50
main: LODD OP1: push
      LODD OP2: push
      LODD OP3: push
      CALL min:
      INSP 2
      STOD OPRES
      HALT
min:  LODL 1; OP1
      SUBL 2; OP2 - OP1
      JPOS op1small
      SUBL 3; OP3 - OP1
      JPOS op1small
op1small: 
      LODL 1
      RETN ; OP1

I'm pretty new to Mic-1 and would like to get any input on this Mic-1 code above. Is there a better or shorter way I can find a min of three numbers in Mic-1?

Answer 1

Min... ish

Is there a better or shorter way I can find a min of three numbers in Mic-1?

Maybe, but first you should be finding the min of three numbers because right now, that's not what is happening.

This is what your current assembly code looks like translated to a pseudo-code:

ac = OP1
ac -= OP2
if ac > 0, return OP1
ac -= 3
if ac > 0, return OP1
return OP1

Try following this through with some example numbers. Still don't understand where you are going wrong? Look at this example again with some mo

; OP1 = 3, OP2 = 2, OP3 = 1
ac = 3
ac -= 2 ; ac is now 1
; ac is > 0, so jump passes and OP1 is returned when OP3 should be instead

See it now? This was probably overlooked due to the fact that you did not thoroughly test your code. It is important to test even the most extreme cases to make sure that your code is cleaned.

Now we need to re-write your code. First off, let's break down your code: instead of trying to find the min of just three numbers, why not try to find the min of two numbers? Then, this subroutine could be used in other min-based subroutines.

I think that the min subroutine would now look like this:

min2:
    LODL 1 ; ac = OP1
    SUBL 2 ; ac -= OP2
    JPOS min2_op2small ; if ac > 0

    LODL 1
    RETN
op2small:
    LODL 2
    RETN

If you are having trouble understanding how this works, try plugging in some values in your head. Here is a run down of what it is doing

1. Store OP1 in the accumulator.
2. Subtract OP2 from the accumulator.
3. If the accumulator is negative, then return OP1.
4. If the accumulator is positive, then return OP2.

Now that we have this basic min subroutine, we can the subroutine for finding the min of 3 numbers.

Using our handy-dandy min2 sub, this new subroutine can simply use the min2 sub to determine what is the greater of the three values:

1. Find the min2 of OP1 and OP2
2. Compare the lesser one with OP3
3. Return the lesser one.

Your current code already follows this structure. However, as show above, it doesn't quite do what it seems.

---

Comments

You seem slightly confused about how this "architecture" works, judging by your comments. In particular, these ones:

  SUBL 2; OP2 - OP1
  ...
  SUBL 3; OP3 - OP1

No; you aren't subtracting 1st parameter from the 2nd and 3rd ones here. In reality, these two statements are the equivalent of

\$(OP1-OP2)-OP3\$

Why is it like this and not how you have indicated it? Here is what your code is doing, minus the conditionals:

1. Load the accumulator with OP1
2. Subtract OP2 from the accumulator.
3. Subtract OP3 from the accumulator.

The accumulator is a register that is used to hold a single value that is often the result of arithmetic. More simple instruction sets (such as this one) force any arithmetic to be done with one of the operands being the accumulator.

See what the difference is? Your comments seemed to act as if there were no conditional whatsoever. More accurate comments would be:

SUBL 2; ac = OP1 - OP2
...
SUBL 3; ac = (OP1 - OP2) - OP3

Answer 2

In answering this question, I wrote a combination simulator/debugger which can be used for testing out the MAC1 language.

One thing to keep in mind when programming in assembly language in general is that if you can arrange data so that it's already where you need it when you need it, you will save a number of instruction by not having to rearrange items so much. This program was constructed with exactly that notion in mind.

First, I used the simulator/debugger to put three numbers, 3, 0x50 and 0x109 into locations 1, 2 and 3 in memory.

m 0 3 50 109 q

It then assembles a short program at location 0x50 which calls a subroutine at location 0x100 which finds the smallest of the three passed numbers and returns it in the ac register.

The program at 0x50 is almost like yours, but correctly restores the stack (if you push 3 items, you need to adjust the stack by 3 and not 2, thus INSP 3 instead of INSP 2.)

a50 
LODD 1 
PUSH 
LODD 2 
PUSH 
LODD 3 
PUSH 
CALL 100 
INSP 3 
STOD 0 
HALT FF 
q

The subroutine at 0x100 is this:

a100 
LODL 1 
SUBL 2 
JNEG 105 
LODL 2 
STOL 1 
LODL 1 
SUBL 3 
JNEG 10A 
LODL 3 
RETN 
LODL 1 
RETN 
q

To make it easier to see where the jumps are going, here's the version with addresses:

0100: LODL 0x0001
0101: SUBL 0x0002
0102: JNEG 0x0105
0103: LODL 0x0002
0104: STOL 0x0001
0105: LODL 0x0001
0106: SUBL 0x0003
0107: JNEG 0x010a
0108: LODL 0x0003
0109: RETN
010a: LODL 0x0001
010b: RETN

We can set up the PC register to point to the program:

rpc 50

And then set the stack pointer to 0x20 which is an arbitrary but convenient location.

rsp 20

Now we can execute the program using the g (Go) command which will execute starting at the current value of PC until it encounters a HALT instruction. (Alternatively, you can step through instruction at a time using the s (Step) command.)

g

Finally, we can look at the memory starting at location 0:

d

The result should look like this:

0000: 0003 0003 0050 0109 0000 0000 0000 0000 
0008: 0000 0000 0000 0000 0000 0000 0000 0000 
0010: 0000 0000 0000 0000 0000 0000 0000 0000 
0018: 0000 0000 0000 0000 0057 0050 0050 0003 

And we can examine the registers by using the r (Registers) command:

r

With this result:

> PC = 0x005a  SP = 0x0020  AC = 0x0003

The way the routine works is to first compare the last two numbers pushed onto the stack using subtraction, as your attempt did. If the last number (the one loaded to by LODL 1) is smaller, we move onto the third number. If the middle number (LODL 2) is smaller, we overwrite the last number loaded since we won't need it any more anyway. Then another subtraction is done to compare the smallest of the last two pushed (which is now loaded using LODL 1) with the third number (LODL 3). Again based on the sign of the result, we load the smallest of those two numbers into the AC register and return.