Karatsuba Multiplication

Source

This multiplication algorithm is particularly important for dealing with large numbers and reducing the computation time by using the concept of divide and conquer!

Traditional multiplication has the running time O(n²) while the Karatsuba algorithm is O(n^(1.59)).

Source

So how does this algorithm work?

We’ll solve this using an example: X = 5634 and Y = 1278

In X: let a = 56 and b = 34
In Y: let c = 12 and d = 78

Now, we compute the following:
1. (a*c) = 672
2. (b*d) = 2652
3. (a+b)*(c+d) = 8100
4. compute [3]-([1]+[2]) = 8100-(672+2652) = 4776

Finally, we compute:
(672 * 10⁴) + (2652) + (4776 * 10²)

6 7 2 0 0 0 0
0 0 0 2 6 5 2
+ 4 7 7 6 0 0
— — — — —
7 2 0 0 2 5 2
— — — — —

This formula can be generalised as a recursive formula as given below:

X = a * 10^(n/2) + b
Y = c * 10^(n/2) + d

so X * Y = (a * c) * 10^n + ((a * d) + (b * c)) * 10^(n/2) + (b * d)

Now, Gauss’ trick comes to our rescue while computing these values.
Instead of having 4 multiplication operations, 3 multiplication operations are sufficient for this algorithm.

(a * d) + (b * c) = (a + b) * (c + d) — (a * c) — (b * d)

Thus, this algorithm implements divide and conquer with an optimized way to calculate the product of two numbers.

We can use this for large numbers too by treating the numbers as strings instead of integer values and performing the above steps.

Pretty cool right?