Karatsuba algorithm

Key of the Process

The basic step of Karatsuba's algorithm is a formula that allows us to compute the product of two large numbers x and y using three multiplications of smaller numbers, each with about half as many digits as x or y, plus some additions and digit shifts.

Let x and y be represented as n-digit strings in some base B. For any positive integer m less than n, one can split the two given numbers as follows

x = x₁B^m + x₀

y = y₁B^m + y₀

where x₀ and y₀ are less than B^m. The product is then

xy = (x₁B^m + x₀)(y₁B^m + y₀)

= z₂ B^2m + z₁ B^m + z₀

where

z₂ = x₁y₁

z₁ = x₁y₀ + x₀y₁

z₀ = x₀y₀.

Example

To compute the product of 1234 and 5678, choose B = 10 and m = 2. Then

12 34 = 12 × 10² + 34

56 78 = 56 × 10² + 78

z₂ = 12 × 56 = 672

z₀ = 34 × 78 = 2652

z₁ = (12 + 34)(56 + 78) - z₂ - z₀ = 46 × 134 - 672 - 2652 = 2840

result = z₂ × 10^2×2 + z₁ × 10² + z₀ = 672 × 10000 + 2840 × 100 + 2652 = 7006652.