# 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, 2013 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, 2013 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, 2013 at 18:14
• Edited. The address is definitely a constant within the instruction. Apr 8, 2013 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, 2013 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, 2013 at 18:25
• I believe they are Turing-complete, compare en.wikipedia.org/wiki/One_instruction_set_computer Apr 8, 2013 at 18:58
• Note that the one instruction computer requires unlimited resources.
– Kaz
Apr 8, 2013 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, 2013 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, 2013 at 19:36