# Implementing multiplication

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]
• 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]

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]
• BZ Rx, Ry, Address [Branch to Address If Rx == Ry ]

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.

• tell us more about your architecture... where do the results of Add Rx, Ry go (presumably they overwrite Rx or Ry)? Are addresses immediates (i.e. constants stored in the instruction)? Apr 8 '13 at 17:54
• Added info to OP. I'm a bit confused about the address immediate thorough. What do you mean by constant stored in the instruction? Apr 8 '13 at 18:02
• Express your instruction semantics using a high level Register Transfer Language... for example Add Rx, Ry might be Rx <= Rx + Ry... it sounds like "address" is a 4-bit constant stored in the instruction since you've said you have a 16 possible addresses in your RAM. An "immediate" is just what you call a constant that is embedded in an machine instruction. Apr 8 '13 at 18:14
• Edited. The address is definitely a constant within the instruction. Apr 8 '13 at 18:23
• Since jumps and branches use the same size addresses as load and store, I presume that both code and data are stored in the 16-byte RAM. That doesn't leave much room to implement multiplication. Apr 8 '13 at 18:38

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.

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

  Add R2,R2
Bnc Skip
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.

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.

• What would it take for it to become turing complete? Shift? Apr 8 '13 at 18:25
• I believe they are Turing-complete, compare en.wikipedia.org/wiki/One_instruction_set_computer Apr 8 '13 at 18:58
• Note that the one instruction computer requires unlimited resources.
– Kaz
Apr 8 '13 at 19:11
• @pjc50 i mean you could trivially implement multiplication for two eight bit numbers with a 2^16 entry table of 16-bit values... Apr 8 '13 at 19:35
• @YamatoC Shift would at least allow you to emulate multiplication iteratively in 'the natural way'... I'm not much of a theoretician so I was just guessing that it is not Turing Complete... Apr 8 '13 at 19:36