# Karatsuba Multiplication

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)).

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 -(+) = 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?

--

--

--

## More from Anjaneya Tripathi

Live. Learn. Laugh. CS Undergrad at NIT Trichy

Love podcasts or audiobooks? Learn on the go with our new app.

## Why the Binomial Coefficient is Central to Algebra, Probability, Combinatorics and Number Theory ## Common special characters and Unicode symbols to copy-paste for mathematics…  ## Infinity Model of the Universe(Part-4 Finale) ## Estimate any DC Motor Transfer Function ## What is the earliest a team can win a title or be relegated? ## Descriptive statistics and probability formulas  ## Anjaneya Tripathi

Live. Learn. Laugh. CS Undergrad at NIT Trichy

## LeetCode 2095- Delete the Middle Node of a Linked List ## JDK vs JRE vs JVM: Key Differences ## 02. A Trip to Objectville 