Karatsuba algorithm

The basic step of Karatsuba's algorithm is a formula that allows one to compute the product of two large numbers ${\displaystyle x}$ and ${\displaystyle y}$ using three multiplications of smaller numbers, each with about half as many digits as ${\displaystyle x}$ or ${\displaystyle y}$, plus some additions and digit shifts. This basic step is, in fact, a generalization of a similar complex multiplication algorithm, where the imaginary unit i is replaced by a power of the base.

Let ${\displaystyle x}$ and ${\displaystyle y}$ be represented as ${\displaystyle n}$-digit strings in some base ${\displaystyle B}$. For any positive integer ${\displaystyle m}$ less than ${\displaystyle n}$, one can write the two given numbers as

${\displaystyle x=x_{1}B^{m}+x_{0},}$

${\displaystyle y=y_{1}B^{m}+y_{0},}$

where ${\displaystyle x_{0}}$ and ${\displaystyle y_{0}}$ are less than ${\displaystyle B^{m}}$. The product is then

${\displaystyle {\begin{aligned}xy&=(x_{1}B^{m}+x_{0})(y_{1}B^{m}+y_{0})\\&=z_{2}B^{2m}+z_{1}B^{m}+z_{0},\\\end{aligned}}}$

where

${\displaystyle z_{2}=x_{1}y_{1},}$

${\displaystyle z_{1}=x_{1}y_{0}+x_{0}y_{1},}$

${\displaystyle z_{0}=x_{0}y_{0}.}$

These formulae require four multiplications and were known to Charles Babbage.[4] Karatsuba observed that ${\displaystyle xy}$ can be computed in only three multiplications, at the cost of a few extra additions. With ${\displaystyle z_{0}}$ and ${\displaystyle z_{2}}$ as before one can observe that

${\displaystyle z_{1}=(x_{1}+x_{0})(y_{1}+y_{0})-z_{2}-z_{0}.}$

An issue that occurs, however, when computing ${\displaystyle z_{1}}$ is that the above computation of ${\displaystyle (x_{1}+x_{0})}$ and ${\displaystyle (y_{1}+y_{0})}$ may result in overflow (will produce a result in the range ${\displaystyle B^{m}\leq {\text{result}}<2B^{m}}$), which require a multiplier having one extra bit. This can be avoided by noting that

${\displaystyle z_{1}=(x_{0}-x_{1})(y_{1}-y_{0})+z_{2}+z_{0}.}$

This computation of ${\displaystyle (x_{0}-x_{1})}$ and ${\displaystyle (y_{1}-y_{0})}$ will produce a result in the range of ${\displaystyle -B^{m}<{\text{result}}<B^{m}}$. This method may produce negative numbers, which require one extra bit to encode signedness, and would still require one extra bit for the multiplier. However, one way to avoid this is to record the sign and then use the absolute value of ${\displaystyle (x_{0}-x_{1})}$ and ${\displaystyle (y_{1}-y_{0})}$ to perform an unsigned multiplication, after which the result may be negated when both signs originally differed. Another advantage is that even though ${\displaystyle (x_{0}-x_{1})(y_{1}-y_{0})}$ may be negative, the final computation of ${\displaystyle z_{1}}$ only involves additions.

To compute the product of 12345 and 6789, where B = 10, choose m = 3. We use m right shifts for decomposing the input operands using the resulting base (B^m = 1000), as:

12345 = 12 · 1000 + 345

6789 = 6 · 1000 + 789

Only three multiplications, which operate on smaller integers, are used to compute three partial results:

z₂ = 12 × 6 = 72

z₀ = 345 × 789 = 272205

z₁ = (12 + 345) × (6 + 789) − z₂ − z₀ = 357 × 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538

We get the result by just adding these three partial results, shifted accordingly (and then taking carries into account by decomposing these three inputs in base 1000 like for the input operands):

result = z₂ · (B^m)² + z₁ · (B^m)¹ + z₀ · (B^m)⁰, i.e.

result = 72 · 1000² + 11538 · 1000 + 272205 = 83810205.

Note that the intermediate third multiplication operates on an input domain which is less than two times larger than for the two first multiplications, its output domain is less than four times larger, and base-1000 carries computed from the first two multiplications must be taken into account when computing these two subtractions.

If n is four or more, the three multiplications in Karatsuba's basic step involve operands with fewer than n digits. Therefore, those products can be computed by recursive calls of the Karatsuba algorithm. The recursion can be applied until the numbers are so small that they can (or must) be computed directly.

In a computer with a full 32-bit by 32-bit multiplier, for example, one could choose B = 2³¹ = 2147483648, and store each digit as a separate 32-bit binary word. Then the sums x₁ + x₀ and y₁ + y₀ will not need an extra binary word for storing the carry-over digit (as in carry-save adder), and the Karatsuba recursion can be applied until the numbers to multiply are only one-digit long.

Karatsuba's original formula and other generalizations are themselves symmetric. For example, the following formula computes

${\displaystyle c(x)=c_{4}x^{4}+c_{3}x^{3}+c_{2}x^{2}+c_{1}x+c_{0}=a(x)b(x)=(a_{2}x^{2}+a_{1}x+a_{0})(b_{2}x^{2}+b_{1}x+b_{0})}$

with 6 multiplications in ${\displaystyle {\text{GF}}(2)[x]}$, where ${\displaystyle {\text{GF}}(2)}$ is the Galois field with two elements 0 and 1.

${\displaystyle {\begin{aligned}\left\{{\begin{array}{l}c_{0}=p_{0},\\c_{1}=p_{012}+p_{02}+p_{12}+p_{2},\\c_{2}=p_{012}+p_{01}+p_{12},\\c_{3}=p_{012}+p_{01}+p_{02}+p_{0},\\c_{4}=p_{2},\end{array}}\right.\end{aligned}}}$

where ${\displaystyle p_{i}=a_{i}b_{i},\ \ p_{ij}=(a_{i}+a_{j})(b_{i}+b_{j})}$ and ${\displaystyle p_{ijk}=(a_{i}+a_{j}+a_{k})(b_{i}+b_{j}+b_{k})}$. We note that addition and subtraction are the same in fields of characteristic 2.

This formula is symmetrical, namely, it does not change if we exchange ${\displaystyle a}$ and ${\displaystyle b}$ in ${\displaystyle p_{i},\ \ p_{ij}}$ and ${\displaystyle p_{ijk}}$.

Based on the second Generalized division algorithms ,[5] Fan et al. found the following asymmetric formula:

${\displaystyle {\begin{aligned}\left\{{\begin{array}{l}c_{0}=p_{0}\\c_{1}=p_{012}+p_{2}+m_{4}+m_{5}\\c_{2}=p_{012}+m_{3}+m_{5}\\c_{3}=p_{012}+p_{0}+m_{3}+m_{4}\\c_{4}=p_{2},\end{array}}\right.\end{aligned}}}$

where ${\displaystyle m_{3}=(a_{1}+a_{2})(b_{0}+b_{2}),\ \ m_{4}=(a_{0}+a_{1})(b_{1}+b_{2})}$ and ${\displaystyle m_{5}=(a_{0}+a_{2})(b_{0}+b_{1})}$.

It is asymmetric because we can obtain the following new formula by exchanging ${\displaystyle a}$ and ${\displaystyle b}$ in ${\displaystyle m_{3},\ \ m_{4}}$ and ${\displaystyle m_{5}}$.

${\displaystyle {\begin{aligned}\left\{{\begin{array}{l}c_{0}=p_{0}\\c_{1}=p_{012}+p_{2}+m_{4}+m_{5}\\c_{2}=p_{012}+m_{3}+m_{5}\\c_{3}=p_{012}+p_{0}+m_{3}+m_{4}\\c_{4}=p_{2},\end{array}}\right.\end{aligned}}}$

where ${\displaystyle m_{3}=(a_{0}+a_{2})(b_{1}+b_{2}),\ \ m_{4}=(a_{1}+a_{2})(b_{0}+b_{1})}$ and ${\displaystyle m_{5}=(a_{0}+a_{1})(b_{0}+b_{2})}$.