Multiply two large numbers in under 1000 instructions using reduced ISA with only 7 registers

Question

Is it possible to multiply two large (15 bit) numbers efficiently (in under 1000 instructions) using the following ISA:

add          //add <reg1> <reg2> <reg3>: add contents of registers 1 and 2 and store in register 3
nand         //nand <reg1> <reg2> <reg3>: nand (negated logical and) contents of registers 1 and 2 and store in register 3
beq          //beq <reg1> <reg2> <label>: if the contents of registers 1 and 2 are equal, jump to label
load         //load <reg2> <label>: load reg2 with content from label
nope         //nope: do nothing
halt         //halt: end program
occupy       //<label> occupy off: label will take value off (between -32768 and 32767)

The memory addresses are 0-indexed, and any occupy statements must come after a halt. For example, a valid program may be:

        load    0    1    ten    //register1 = 10
        load    1    2    m1     //register2 = -1
here    add     1    1    1      //register1 = register1+register1 = 20
        beq     0    0    end    //if(register0 = register0), go to end
end     halt
ten     occupy  10
m1      occupy  -1

I know there are efficient methods using binary multiplication (and the nand operator, presumably), but I'm having trouble constructing a program that can multiply large integers accurately.

Any ideas?

If there is anything that needs to be clarified, please let me know. Thank you.

Answer 1

Here is a solution. For clarity I refer to registers by letters instead of numbers, and use expression notation to write the instructions. The expression "p # q" means the negated AND of p and q.

; Computes the product of nonnegative integers a and b and stores it in s
z <- 0                          ; z == 0
s <- 0                          ; stores the product
j <- 1                          ; a power of 2, determines which bit of b
                                ; the program is looking at
c <- a + z                      ; c == a * j

loop:
  if b == z goto endprogram       ; end if there are no 
                                  ; remaining bits in b
  d <- j # b
  d <- d # d                      ; d == j & b       
  if d == z goto noadd
    s <- s + c                    ; the bit determined by j is set in b,
                                  ; so add c to the product s
  noadd: 
  d <- j # j
  b <- b # d
  b <- b # b                      ; b := b & ~j         
  j <- j + j                      ; j := 2j
  c <- c + c                      ; c := 2c
  if z == z goto loop
endprogram:
halt