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.
The above explanation is confusing at the first glance.
ReplyDeleteSomewhere, B=10 and somewhere B=4488
Please edit.
Btw, nice algorithm.