Here is a cool algorithm that calculates multiplication by addition and bit-shifting only. This method is exponentially faster than the literal implantation of multiplication in which x is added y times.

To prove that it works, consider the function

f(a,b,c) = ab + c

before the loop, during the loop, and after the loop.

Before the loop, we have

f = xy + 0 = xy

During the loop, we have for even a,

a' = a/2

b' = 2b

c' = c

f' = ab + c = xy

and for odd a,

a' = (a-1)/2

b' = 2b

c' = c + b

f' = ab + c = xy

Hence, it must be the case that f(a,b,c) = xy for any number of iterations in the loop by induction. Now, the ending condition of the loop yields a = 0, so it must be the case that

c = f - ab = f = xy

In other words, the return value is guaranteed to be the product of the input x and y!

## No comments:

## Post a Comment