Multiplication with repeated Addition Intel 4004

Question

Could anyone tell me how to multiply two 4 Bit binary numbers with repeated addition on the Intel 4004?

the addition code is:

FIM R0R1, 0x78 ; initialize: R0=8 R1=7
LD R0 ; load R0 into accumulator
ADD R1 ; add R1 into accumulator
XCH R1 ; and store in R1 done:
JUN done ; endless loop as end of program

I think logic is that: Multiplication can be done by repeated addition.

1. Initialize memory pointer to data location.
2. Move multiplicand to a register.
3. Move the multiplier to another register.
4. Clear the accumulator.
5. Add multiplicand to accumulator
6. Decrement multiplier
7. Repeat step 5 till multiplier comes to zero.
8. The result, which is in the accumulator, is stored in a memory location.

instruction set is in this link to reach: http://www.e4004.szyc.org/iset.html

I spent so much time to understand, but i can not. I would be really so appreciated if somebody helps.

Answer 1

The way you'd like to do this is very slow! Imagine you'd like to multiply two 32-bit numbers (you can do this with the 8080, the 4004 has not enough memory): When both numbers are larger than 1000000 the multiplication would take a lot of time.

A better algorithm would be like this:

  set result = 0
  set A = first number
  set B = second number
loop:
  if the lowest bit of A is 0 then jump to "no_add"
  add B to result
no_add:
  shift A right (logic, not arithmetic!) one bit
  shift B left one bit
  if A is not zero then jump to "loop"

Using a "rotate through carry" operation you may do the "shift A right one bit" and the "check the (previous) value of the lowest bit of A" operations using one instruction!

Answer 2

You do not need RAM memory to do this. The 4004 contains several index registers to use as memories.

The difficulty is that all things must have been done with the accumulator, since there are very few opcodes that manipulate the index registers: the loop, the arithmetics, the flag test - so you have to make heavy use of saving the accumulator to index registers and loading it back into accumulator.

That is: 1. the loop counter (which has to be decremented and checked if it is "0" (by testing the carry bit). 2. the arithmetics: adding a number "x" n-times to itself (load it from index register and - after addition is complete - store it back there)

Another constaint is that you only can multiply within a 4 or 8 bit range (which would result in a longer program because you have to use double-registers). So you can just multiply from 1x1 to 3x4 (or 4x3) - whitin the 4 bit range.

Since the 4004 seems to have no bit shifting opcode the multiply-by-adding seems to be the best way.