Thursday, 23 October 2014

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 Bm where m<n
Say B=10 and m=2
So resulting base Bm = 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 * B2m + R * Bm + 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.