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.
The above explanation is confusing at the first glance.

ReplyDeleteSomewhere, B=10 and somewhere B=4488

Please edit.

Btw, nice algorithm.