The Karatsuba multiplication algorithm is named after the Russian mathematician Anatoly Karatsuba. It uses a divide and conquer approach that gives it a running time improvement over the standard “grade-school” method. Read on for Python implementations of both algorithms and a comparison of their running time.

The problem

You are given two integers x and y. Both have a length of length n digits. You want to find the product of these two numbers. So you want to find z in: z = x * y

The size of the problem is n. The more digits in x and y the harder the problem.

Above I have assumed that both x and y have the same digit length. The problem can be extended to cases where they are not the same number of digits. To do this just add the appropriate number of zeros to the left of the smaller of the two integers.

The “grade-school” algorithm

This is probably the method for multiplying numbers that you learned in school.

The algorithm is:

1. Break the second number into units, tens, hundreds, thousands etc.
2. Start with the units. Multiply the units from the second number by each digit in the first number.
3. Do the same with the tens but add a zero before your answer.
4. Do the same with the hundreds but add two zeros before your answer.
5. Continue through the digits of the second number adding an additional zero before your answer each time.
6. Sum all these partial multiplications to get the final answer.

Grade-school example

Let’s run through the grade-school algorithm on two four digits integers. 2925 x 6872.

First you tackle the units of the second number (2):

Don’t forget to carry the 1s!

Then the tens (7), the hundreds (8) and the thousands (6). Don’t forget to add another zero each time:

Then sum all the partial multiplications to get 20,100,600:

Grade-school in Python

This iterative process can be coded in Python with a double for loop. The first for loop works through the digits in the second number. The second (nested) for loop works through the digits in the first number.

Grade-school running time

When thinking about running times we need to be clear what we actually mean by running time. All the calculations in the algorithm can broken down into single digit additions, subtractions and multiplications. This is what we will base our running time analysis on.

The running time is the total single digit addition, subtraction and multiplication calculations used to compute an answer. We will call an algorithm faster if it uses fewer of these basic operations to compute an answer.

How many of these basic calculations does the grade-school algorithm need? Each partial multiplication requires n single digit multiplications. One for each digit in the first number. It also needs at most another n single digit additions when numbers are carried. So each partial multiplication uses at most 2n of the basic operations.

There are n partial multiplications. One for each digit in the second number. So the maximum number of basic operations needed to calculate all partial multiplications is 2n².

How about adding all the partial multiplications? How many basic operations will that use? At most 2n² are needed.

In total the maximum number of basic operations the grade-school algorithm needs to use is 4n². This is the worst case running time. If we get lucky and multiply two numbers that don’t need lots of “carrying” then fewer calculations will be needed.

Karatsuba’s algorithm

The key to understanding Karatsuba’s multiplication algorithm is remembering that you can express x (an n-digit integer) in the following way:

For example you can express 2925 as:

You can use this if you want to multiply x by another n-digit integer y:

Then x multiplied by y can be written as:

This is where Karatsuba found a neat trick. He found a way to calculate ac, bd and (ad + bc) with just three multiplications (instead of four).

To see why think about:

If you have already calculated ac, and bd then (ab + bc) can be calculated by subtracting ac and bd from (a+b)(c+d):

You can use Karatsuba’s trick recursively to compute the multiplication.

Here’s Karatsuba’s algorithm:

1. Break the two integers x and y into a, b, c and d as described above
2. Recursively compute ac
3. Recursively compute bd
4. Recursively compute (a + b)(c + d)
5. Calculate (ab + bc) as (a + b)(c + d) – ac – bd
6. Let A be ac with n zeros added to the end
7. let B be (ab + bc) with half n zeros added to the end
8. The final answer is A + B + bd

By “recursively compute” I mean call the algorithm again to calculate these multiplications. For recursion you always need a base case to prevent an endless loop. The base case here is when the two integers x and y are single digit. In this case the algorithm just calculates and and returns their product.

Beware: this is only valid for integers with an even number of digits. You can easily extend it to be correct for odd digit integers. You just need to make sure there is consistency between the number of digits in b and d and the zeros you add to get A and B.

Karatsuba example

Let’s apply the Karatsuba algorithm to a simple example. We want to multiply 2925 x 6872 (again!)

First break the 2925 into 2 chunks, a = 29 and b = 25. Then break the second integer into two chunks, c = 68 and d = 72:

Then calculate ac as 29 x 68 = 1972, bd as 25 x 72 = 1800 and (a + b) x (c + d) as (29 + 25) x (68 + 72) = 54 x 140 = 7560.

Next subtract ac and bd from the final quantity to get (ad + bc) = 7560 – 1972 – 1800 = 3788.

Add 4 zeros to the end of ac to get 19,720,000 call this number A.

Add 2 zeros to the end of (ab + cd) to get 378,800 call this number B.

Then sum A (19,720,000), B (378,800) and bd (1800) to get 20,100,600. Which matches what we got with the grade-school algorithm.

Recursive Karatsuba in Python

Here’s my implementation of Karatatubs’s algorithm. The zeroPadd() function defined above in the code for the grade-school algorithm is used. k is the variable I use to hold the value of (a + b)(c + d). Also notice the use of recursion when calculating ac, bd and k. This works because a base case is specified for single digit integers.

Karatsuba running time

To find an upper bound on the running time of Karatsuba’s algorithm we can use the master theorem. The master theorem states that the running time of a recursive algorithm is:

Where:

• T(n) the running time of the algorithm
• a is the number of recursive calls used
• b is the scale that the problem size shrinks by with each recursive call
• O(n^d) represents the work done by the algorithm outside of the recursive calls

For Karatsuba’s algorithm we can see there are three recursive calls. On lines 25, 26 and 27. So a = 3.

Each time a recursive call is made it is on a problem of half the size. This is because of the way each number is broken into two even sized chunks. So b = 2.

Outside of the recursive calls Karatsuba’s algorithm uses a constant number of addition and subtractions. Six in total. On lines 27, 29 and 30. Each of which will use at most 3n single digit additions. So we can say the work done outside recursive calls is O(n). So d = 1.

Because a = 3 and db = 2 we know a < bd. This means the last case of the master theorem is used. So the running time of Karatsuba’s recursive algorithm is:

The grade-school algorithm had a worst case running time of 4n². 4n² is O(n²). Karatsuba’s algorithm is faster with O(n^1.585) running time. Nice work Karatsuba!