Multiplication Algorithm

[The LoserKing]

Hi,
   When I was at uni I had to write a multiplication algorithm. The standard solution was repeated addition. Unfourtunately I didn't come up with this algorithm until a few hours after I handed in my assignment, although it is relatively simple. I would like to know if anything like this is used in the real world?

In pseduo code it goes a like this

Multiplier = smallest number
Multiplicand = largest number
total = 0

while(multiplier > 0)
do
  shift right (multiplier)
  if(carryflag == 1)then
    total += multiplicand
  endif
  shift left  (multiplicand)
enddo

print total

This is just the guts of the algorithm and doesn't account for a multiplicand that shifts to far left. In which case part of it needs to be stored in another register. There was an optimization for the power of 2 but I can't recall what it was anymore. I ended up getting schizophrenia so I never made it through uni so I can't ask anyone in the real world.

[Ratch]

The LoserKing,

I would like to know if anything like this is used in the real world?

     Only for embedded processors that have no MUL instruction.  A MUL instruction is much faster and easier that iterated bit fiddling.  Ratch

[dsouza123]

Lets check for large integer multiplication ie two 1024 bit numbers (32 dwords),
multiplied together resulting in a 2048 integer (64 dwords).

Multiply by adding shifted copies:
Set the total to 0.
Take either number, 1 original and make 7 copies of it, each shifted left by one more bit.
Then use the other number bit by bit, low to high, if it is a 1
then add the appropriate version of the 8 variations to the total.
There would be 7 full length left shifts, to make the copies, could use 7 full length adds instead.
and on average 512 full length adds, (half of the bits == 1),
maximum of 1024, using 1024 bit numbers (32 dwords).

Multiply by multiplying by a dword then adding:
Set the total to 0.
Compared with taking one dword at a time (low to high) of either number,
and multiplying it by the other number, then adding it to the total.
There would be 32 full length multiplies, (1024 32x32 bit multiplies),
with 32 full length carry adds during the multiplication,
and 32 full length,(1024 bit adds), to the total.

[The LoserKing]

Ratch , yeah the assembler we were using had no MUL instruction. Thanks