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.
If there is anything that needs to be clarified, please let me know. Thank you.