Multiplication

Observe that computers work with binary numbers. Each bit has either the value 2ⁿ or zero depending on if 1 or 0 is stored in the memory cell. The sum of all bit values gives the number.

72 = 01001000 <-- Least significant bit
72 = 0*128 + 1*64 + 0*32 + 0*16 + 1*8 + 0*4 + 0*2 + 0*1

From this we can deduce that multiplication by two can be achieved by shifting all bits one step to the left since they will all double in value and the sum must also double. Division by two works by the same principle using shift to the right.

Repeated shifts makes it possible to multiply or divide by 2ⁿ using n shifts.

For a = 72 * 50 we get:

0   0 * 50 =    0   
0   0 * 50 =    0
0   0 * 50 =    0
1   8 * 50 =  400
0   0 * 50 =    0
0   0 * 50 =    0
1  64 * 50 = 3200
0   0 * 50 =    0
-----------------
   72 * 50 = 3600

Interesting, we see that 50 has only been multiplied by 2ⁿ and the only extra operation is addition. So how do we make an optimal algorithm for this?

Equation: answer = a * b

Algorithm (identical to the table):

answer = 0
for n = 0 to 7
  if (a and 2n) then answer = answer + b * 2n
next n

This works fine, but how do we increase the efficiency? We do that by moving things out of the loop, removing unneeded variables and replacing complex slow operations with simpler faster ones.

2ⁿ is a very expensive operation, but as we saw earlier it is identical to multiple shifts.

So...

answer = 0
n = 1
for i = 0 to 7
  if (a and n) then answer = answer + b * n
  n =n << 1
next i

Now we se that b*n has turned into b*2ⁿ and can be replaced by a shift.

answer = 0
n = 1
for i = 0 to 7
  if (a and n) then answer = answer + b
  n = n << 1
  b = b << 1
next i

Now we notice that we AND a with a number that is of the type 2ⁿ, we can instead divide a by 2ⁿ and AND by 1.

answer = 0
n = 1
for i = 0 to 7
  if (a and 1) then answer = answer + b
  a = a >> 1
  n = n << 1
  b = b << 1
next i

Now we see than n is not of any use anymore...

answer = 0
for i = 0 to 7
  if (a and 1) then answer = answer + b
  a = a >> 1
  b = b << 1
next i

Now we notice that a is always zero when we have completed the operation, so i is not needed anymore...

answer = 0
do while a > 0
  if (a and 1) then answer = answer + b
  a = a >> 1
  b = b << 1
loop

We also have achieved that we don't need to test all bits in a if all the remaining bits are 0.

At this point it has reached a stage where it can't be made faster without making it more complex. That usually means it can be faster on average, but it might cause it to be slower on some numbers.