Divide and Conquer: Karatsuba Integer Multiplication

Multiplying numbers is one of the few things we learn while starting on the unique learning journey. The grid method used to perform the multiplication of two numbers is something we grow up doing at least a thousand times.

Yet, we all agree that this method is often time-consuming, especially when numbers involved in the process have a large number of digits. This inefficiency of grid multiplication amplifies when computers try to perform this multiplication. The inefficiency limits the computers to perform large multiplication.

Karatsuba Integer Multiplication is a fast multiplication method proposed by Anatoly Karatsuba in 1960. The method/algorithm proposed is a typical example of the divide-and-conquer algorithm. The procedure is preferred over grid multiplication, especially when numbers involved have many digits in them.

Task Definition

Given two large numbers, a and b, we have to find their product c such that c is

(a*b)

.

Numbers can have a large number of digits. Consider numbers to be represented as an array where the least significant digit is at the lowest index of the array. Each index of the array can hold an integer from 0 to 9 only.

With the task now defined clearly, we can formally start working on the problem and slowly form the solution proposed by Karatsuba.

Addition and Multiplication we Learnt at School

The addition of two numbers having n digits each (consider 0 paddings if one of the numbers has fewer digits) can be easily performed using the school addition method. Here we go from least significant digit to most significant digit, taking the carry each time we add numbers at the same significance level. It should not be difficult to digest if the addition method takes O(n) complexity.

Multiplication of two numbers, each having n digits (again consider 0 paddings if one of the numbers has fewer digits), is performed by the grid method. The first step is to create the grid, which is going over each digit of the first number and performing multiplication with all digits of the other number. Thus making the grid takes

O(n*n)

times itself. Once the grid is completed, we have to perform the last addition of adding all the rows. Since we have n rows and at max

2n+1

cols, the time to solve the problem would be

O(n*n)

. Thus the multiplication method taught in school is of order 2, which is not the fastest way.

First Attempt at the Problem

Consider a simple algorithm aimed at solving the multiplication problem slightly differently. Split the numbers into two halves. Let us call the part containing the less significant digits as left half and the other being the right half. If the number of digits is not even, we can add 0 to the right. In this way, dividing the number into two halves becomes easier, and both halves have the same length. Here is the illustration describing how the split is performed.

Once we perform this splitting, we get four numbers each of half the original length. Our goal is to represent the product of the original two numbers in the form of these four numbers. This is how we can express it -

So now we have reduced the problem of multiplication of two numbers, each containing N digits, to the problem of multiplying four numbers of size

N/2

each. Note that addition is not the bottleneck since it is a linear time algorithm. Also, note that multiplication by a power of 10 means appending 0s at the end of the array, which is again linear. Thus the main work is done in finding out the four products which are present in the equation.

Unfortunately, this does not improve over the naive way of performing the multiplication using the grid method. Using Master's theorem, we can find this solution's time complexity, which is the same as

O(n*n)

.

Arriving at Karatsuba Algorithm

Our previous attempt to reduce the time complexity of the multiplication seems to went in vain. But we could have gained some performance if there were fewer multiplications required. So is there any other way that requires fewer multiplications? It turns out we need not go far looking for another way. Our failed solution holds the potential.

A detailed analysis would reveal that, in reality, we only need three multiplications to find the product of two numbers. Are we not convinced? Here is how we can do it -

Thus the problem is now solvable using three multiplications of size N/2. Additions are never a bottleneck, and thus the blocking operation is the calculating those three products. Using the Master's theorem, the time complexity of this new algorithm is

O(n^1.58)

. And this way of performing multiplication is known as Karatsuba multiplication.

Final Words

This completes the explanation of the Karatsuba algorithm. Do like if this blog helped you. 😊