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?

--

--

--

Live. Learn. Laugh. CS Undergrad at NIT Trichy

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

Recommended from Medium

Why the Binomial Coefficient is Central to Algebra, Probability, Combinatorics and Number Theory

Common special characters and Unicode symbols to copy-paste for mathematics…

What is so hard about this IMO problem?

Bottom row is 6, 1, 10, 8. Second row is 5, 9, 2. Third row is 4, 7. Top row is 3.

Variance

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

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Anjaneya Tripathi

Anjaneya Tripathi

Live. Learn. Laugh. CS Undergrad at NIT Trichy

More from Medium

LeetCode 2095- Delete the Middle Node of a Linked List

JDK vs JRE vs JVM: Key Differences

02. A Trip to Objectville

String Data Structure Practice Problems: How to verify a character after a letter in a given string…