Karatsuba multiplication

Multiplying two n-digit numbers the way it is taught at school takes about n² single-digit products. For centuries nobody knew a faster way. In 1960 Anatoly Karatsuba, a student in Moscow, found one with a small piece of algebra: three multiplications of half-size numbers instead of four.

Multiplying digit by digit

The schoolbook method multiplies every digit of one number by every digit of the other, writes the products in shifted rows, and adds the rows. Two numbers of n digits give n × n = n² digit products, plus the additions, so it costs O(n²).

For numbers of a few digits that is nothing. But cryptography multiplies numbers of hundreds of digits, and computing π to a million places multiplies numbers of a million digits. There, n² is a trillion, and the method matters.

Splitting does not help by itself

Split each number into a high half and a low half. With m digits in the low half, write x = a × 10ᵐ + b and y = c × 10ᵐ + d. For 1321 and 2213 with m = 2: a = 13, b = 21, c = 22, d = 13. Then

x × y = (a × c) × 10²ᵐ + (a × d + b × c) × 10ᵐ + b × d.

Multiplying by 10ᵐ only adds m zeros at the end, which costs O(n), and so do the additions. So one product of n digits needs four products of n/2 digits: T(n) = 4 T(n/2) + O(n). Since 4 > 2¹, the leaves win (BIGO-6), and the cost is n to the power log₂ 4, which is n². No better than school. Step through “Plain split: 4 products” in the figure: the 16 one-digit products at the bottom are exactly the schoolbook’s 16.

Three products instead of four

The middle part needs only the sum a × d + b × c, not the two products on their own. Karatsuba noticed that

(a + b) × (c + d) = a × c + a × d + b × c + b × d,

so

The products a × c and b × d are needed anyway. So three products are enough: a × c, b × d and (a + b) × (c + d). The price is a few extra additions and subtractions, which cost O(n). The sums a + b and c + d may have one digit more than the halves, which does not change the cost.

Now T(n) = 3 T(n/2) + O(n). Since 3 > 2¹, the leaves win again, but there are fewer of them: the bottom level has 3 to the power log₂ n products, which equals n to the power log₂ 3. So Karatsuba’s method costs O(n¹·⁵⁸⁵), because log₂ 3 ≈ 1.585. For a million digits, n² is 10¹² and n¹·⁵⁸⁵ is about 3 × 10⁹, over 300 times less.

The code

Here is the method on Python integers, to show its shape. Python’s * is used only when one side is a single digit, or a power of ten (which only adds zeros). divmod(x, p) gives the high and low halves: x // p and x % p.

def karatsuba(x, y):
    """x * y for whole numbers x, y >= 0."""
    if x < 10 or y < 10:
        return x * y                    # a single digit: multiply directly
    m = max(len(str(x)), len(str(y))) // 2
    p = 10 ** m
    a, b = divmod(x, p)                 # x = a * p + b
    c, d = divmod(y, p)                 # y = c * p + d
    ac = karatsuba(a, c)
    bd = karatsuba(b, d)
    middle = karatsuba(a + b, c + d) - ac - bd     # = a*d + b*c
    return ac * p * p + middle * p + bd

In practice the recursion stops well before single digits. A call has a fixed cost (splitting, the three calls, the additions), so on short numbers the schoolbook method is faster. Real programs switch to it below a cutoff, typically a few dozen digits. With digit lists in Python, a cutoff of about 32 digits works well: practice problem 5 asks you to multiply digit lists this way.

Python’s own integers

Python’s int has no size limit, and CPython already uses Karatsuba’s method when both numbers are longer than 70 of its internal digits (each internal digit holds 30 bits, so this is about 630 decimal digits). Below that it uses the schoolbook method, just as the cutoff above. So for real work, use *: it runs in C.

• Toom–Cook splits into 3 parts and needs 5 products instead of 9: n to the power log₃ 5, about n¹·⁴⁶⁵.
• Methods based on the fast Fourier transform (Schönhage and Strassen, 1971) reach about n log n log log n. The library GMP uses all of these, each above its own cutoff. In 2019 Harvey and van der Hoeven reached O(n log n).
• Converting a huge int to text is also costly. Since Python 3.11, str() refuses numbers longer than 4,300 digits unless you raise the limit with sys.set_int_max_str_digits, because a very slow conversion could be used to slow down a server.

The same idea, saving one product out of several, gave Strassen’s matrix multiplication (lesson 2), with 7 block products instead of 8.