Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

closed as off topic by Austin Mohr, Brett Frankel, userNaN, Brandon Carter, Chris Eagle Jan 29 '13 at 7:51

Questions on Mathematics Stack Exchange are expected to relate to math within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

    
Maybe this is a better fit for the computing site? –  Gerry Myerson Jan 29 '13 at 3:25
    
I haven't received much insight there, so I thought I would try here. –  Bob John Jan 29 '13 at 3:26
    
Could you post the link to your stackoverflow post? –  JSchlather Jan 29 '13 at 3:26
    
@JacobSchlather it was closed as "non constructive." However, I've edited the details here. Efficiency seems to be harder to achieve in this program (since adding multiple times takes much too long). –  Bob John Jan 29 '13 at 3:29
1  
@Bob: The usual algorithm isn't repeated addition. –  Hurkyl Jan 29 '13 at 4:02

1 Answer 1

up vote 1 down vote accepted

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
share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.