Quick multiplication

          Multiplication is always an expensive operation to perform for critical and hard real time processor based application. Mathematically multiplication is a result of shifting and addition. KARATSUBA algorithm is a fast multiplication method. Without going into mathematical details I will just give an example.

Say, you have to multiply 9351 * 288

First, we can see max number of digit n = 4

We have to take a base B^m where m<n

Say B=10 and m=2

So resulting base B^m = 100

Now decompose the numbers :

X = 9351 = 93*100 + 51

Y = 288 = 2*100 + 88

P = 93*2 = 186

Q = 51*88 = 4488

R = (93+51) * (2+88) – X – Y = 144 * 90 – 186 – 4488 = 8286

So Result

Res = P * B^2m + R * B^m + Q

= 186 * 10000 + 8286 * 100 + 4488

= 2693088

If you think the intermideate muliplications like (144 * 90) are also big you can apply the same recursively with approriate base.

So, computer programmer enjoy “Divide and Conquer” multiplication and all the competitive exam canditates, you can also conquer.