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.

Contents

# 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:**

- Break the second number into units, tens, hundreds, thousands etc.
- Start with the units. Multiply the units from the second number by each digit in the first number.
- Do the same with the tens but add a zero before your answer.
- Do the same with the hundreds but add two zeros before your answer.
- Continue through the digits of the second number adding an additional zero before your answer each time.
- 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.

def zeroPad(numberString, zeros, left = True):

`"""Return the string with zeros added to the left or right."""`

for i in range(zeros):

`if left:`

numberString = '0' + numberString

`else:`

numberString = numberString + '0'

`return numberString`

def gradeSchoolMultiplication(x, y):

`"""Multiply two integers using the grade-school algorithm."""`

`#convert to strings for easy access to digits`

x = str(x)

y = str(y)

`#keep track of number of zeros required to pad partial multiplications`

zeroPadding = 0

`#sum the partial multiplications as we go`

partialSum = 0

`#loop over each digit in the second number`

for i in range(len(y) -1, -1, -1):

`#keep track of carry for multiplications resulting in answers > 9`

carry = 0

`#partial multiplication answer as a string for easier manipulation`

partial = ''

`#pad with zeros on the right`

partial = zeroPad(partial, zeroPadding, False)

`#loop over each digit in the first number`

for j in range(len(x) -1, -1, -1):

z = int(y[i])*int(x[j])

`z += carry`

`#convert to string for easier manipulation`

z = str(z)

`#keep track of carry when answer > 9`

if len(z) > 1:

carry = int(z[0])

`else:`

carry = 0

`#concatenate final answer to the left of partial string`

partial = z[len(z) -1] + partial

`#if there's any carry left at the end concatenate to partial string`

if carry > 0:

partial = str(carry) + partial

`#sum the partials as you go`

partialSum += int(partial)

`#for the next digit of the second number we need another zero to the right`

zeroPadding += 1

`return partialSum`

## 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 ^{2}*.

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

In total the maximum number of basic operations the grade-school algorithm needs to use is *4n ^{2}*. 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:**

- Break the two integers
*x*and*y*into*a*,*b*,*c*and*d*as described above - Recursively compute
*ac* - Recursively compute
*bd* - Recursively compute
*(a + b)(c + d)* - Calculate
*(ab + bc)*as*(a + b)(c + d) – ac – bd* - Let
*A*be*ac*with*n*zeros added to the end - let
*B*be*(ab + bc)*with half*n*zeros added to the end - 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.

def karatsubaMultiplication(x ,y):

`"""Multiply two integers using Karatsuba's algorithm."""`

`#convert to strings for easy access to digits`

x = str(x)

y = str(y)

`#base case for recursion`

if len(x) == 1 and len(y) == 1:

return int(x) * int(y)

if len(x) < len(y):

x = zeroPad(x, len(y) - len(x))

elif len(y) < len(x):

y = zeroPad(y, len(x) - len(y))

n = len(x)

j = n//2

`#for odd digit integers`

if (n % 2) != 0:

j += 1

`BZeroPadding = n - j`

AZeroPadding = BZeroPadding * 2

a = int(x[:j])

b = int(x[j:])

c = int(y[:j])

d = int(y[j:])

`#recursively calculate`

ac = karatsubaMultiplication(a, c)

bd = karatsubaMultiplication(b, d)

k = karatsubaMultiplication(a + b, c + d)

A = int(zeroPad(str(ac), AZeroPadding, False))

B = int(zeroPad(str(k - ac - bd), BZeroPadding, False))

`return A + B + bd`

## 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*represents the work done by the algorithm outside of the recursive calls^{d})

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 ^{2}*.

*4n*is O(

^{2}*n*). Karatsuba’s algorithm is faster with O(

^{2}*n*) running time.

^{1.585}**Nice work Karatsuba!**

danilochavez says

April 12, 2019 at 5:58 pmI liked your explanation a lot!