Implementing multiplication

Question

I'm trying to implement multiplication in a cpu I designed. I'm trying to achieve this with some conditions. I only two general purpose registers Rx and Ry and these instructions:

• Add Rx, Ry [Add take Rx and Ry to ALU and returns result to Rx]
• LD Rx, address [Load takes the data in RAM from address and loads to Rx]
• STR Rx, address [Store takes data from Rx and stores to address in RAM]
• BZ Rx, Ry, Address [Branch compares the data in two registers. Jumps if equal]
• Jump Address [Jumps to address]

If I only have 2 registers and RAM, is there a way to implement multiplication? I know the general way to implement it is by using shifts but I don't have the implemented and would prefer not to. I was thinking of looping an addition call but I can't seem to get that work since I only have 2 registers.

EDIT: You can select which register by addressing them either 0 or 1. Also, my RAM is only 16 bytes large and the bus is only 8 bits within the CPU.

• Add Rx, Ry [Rx <= Rx + Ry]
• LD Rx, address [Rx <= RAM(address)]
• STR Rx, address [RAM(address) <= Rx]
• BZ Rx, Ry, Address [Branch to Address If Rx == Ry ]
• Jump Address [Jumps to address]

The address is a 4-bit constant stored in the instruction. Rx or Ry are 1 bit. OPCODE is 4 bit with the exception of LD and STR where 4th bit of OPCode refers to register selection.

Answer 1

At minimum, you need a branching instruction which can determine whether the previous addition generated a carry. Also, performance will be improved enormously if you expand your register set to three or four registers.

Start with one operand in R0 and the other in R1. Start with R2 zero.

Repeat the following sequence eight times (first ADD may be skipped on first pass)

  Add R2,R2
  Add R0,R0
  Bnc Skip
  Add R2,R1
Skip:

Note that if the instruction set includes an add-with-carry instruction, using it for the second instruction would cause this instruction sequence to yield a 16-bit result in R0:R2. Further, if R2 starts non-zero, its value times 256 will be added to the outgoing result.

Answer 2

I don't think Add, Load/Store, and Branch If Zero, and Jump are a "Turing Complete" instruction set or whatever. That is to say I don't think you can construct multiplication (among other things) using only these instructions. Just a guess though.