For Great Justice

This Too Shall Pass

Multiplication Workshop

Posted on May 14, 2016
Categories: Code — Tags: none

I’ve been playing Human Resource Machine. It’s awesome! It’s a little silly that I’ve been relaxing after a long day of coding by… doing assembly programming, but it’s a fun game.

Anyway, I’ve been hung up at the optimization challenges for Year 20: Multiplication Workshop.

The challenge: For each two things in INBOX, multiply them and OUTPUT the result. Don’t worry about negative numbers for now.

Optimization challenges:

  1. Use 15 or fewer commands
  2. Complete in 109 or fewer steps.

The first challenge was easy. The second was not. But I’m finally there, so… here’s my solution!

FYI:

  • Register 0 is my counter
  • Register 9 is initialized to “0”.
  • Register 1 is a copy of the number to add in the multiplication loop
  • Register 2 is the final result.

There’s a little bit of trickery. If either input number is a zero, it jumps to an early exit. If the operand being used as a counter is larger than the other operand, we swap them. And to speed up the mulitiplication loop, I negate counter to take advantage of the “jumpn” command, or “jump if the current value in the accumulator is negative”. So the “BUMPUP” instruction increments the counter and copies the new value to the accumulator, and if it’s zero we exit.

Whee!

-- HUMAN RESOURCE MACHINE PROGRAM --

a:
b:
    INBOX         ; read first input
    JUMPZ    f    ; jump to label f if zero
    COPYTO   2
    INBOX         ; read second input
    JUMPZ    g    ; jump to label g if zero
    COPYTO   0
    SUB      2    ; this bit compares the two numbers...
    JUMPN    h
    ; in this branch, the current value of the counter is bigger than the
    ; other operand. Let's switch!
    COPYFROM 0    
    COPYTO   1
    COPYFROM 2
    COPYTO   0
    COPYFROM 1
    COPYTO   2
c:
    ; because register 2 already equals register 1 (instead of "0"),
    ; reduce the counter by one.
    BUMPDN   0
    JUMPZ    e ; jump for an early exit if the counter is zero
    SUB      0 ; make the counter negative for a faster loop
    SUB      0
    COPYTO   0
d:
    COPYFROM 1 ; the main addition loop
    ADD      2
    COPYTO   2
    BUMPUP   0
    JUMPN    d ; we keep looping until the counter is zero
e:
    COPYFROM 2 ; output the value in register two
    OUTBOX  
    JUMP     a ; go back for new input

; This label is if the first value is zero
f:
    INBOX      ; dump
    COPYFROM 9 ; copy zero from register

; This label is used if the second value is zero
g:
    OUTBOX  
    JUMP     b

; This is a shortcut to copy the second operand to the result,
; then jump back to the bit where we negate the counter.
h:
    COPYFROM 2
    COPYTO   1
    JUMP     c
Tags: none