The Karatsuba trick

Let f, g be two univariate polynomials in x with degrees p and q respectively. Let $\mathbb {R}$ be their ring of coefficients. Define

f (x)  =   a_px^p + ^... + a₁x + a₀ (45)

and

g(x)  =   b_qx^q + ^... + b₁x + b₀. (46)

COMPUTING THE PRODUCT f (x)g(x) by the straightforward method requires

• (p + 1)(q + 1) multiplications in $\mathbb {R}$ and
• pq additions in $\mathbb {R}$.

So the complexity of this computation is $\cal {O}$(pq) (in term of operations in $\mathbb {R}$).

Thus the complexity of the computation of the product of two univariate polynomials of degree at most n is $\cal {O}$(n²) (in term of operations in $\mathbb {R}$).

COMPUTING THE SUM f (x) + g(x) is $\cal {O}$(n) (in term of operations in $\mathbb {R}$) if f and g have of degree at most n.

ADDING IS OFTEN CHEAPER THAN MULTIPLYING. So adding polynomials is cheaper than multiplying them. For many rings $\mathbb {R}$ addition is also cheaper than multiplication. So when computing f (x)g(x) let's try to save on the number of multiplications in $\mathbb {R}$.

THE KARATSUBA'S TRICK. Assume f and g have degree (strictly) less than n = 2^k (where k is an integer). The Karatsuba's trick computes the product f (x)g(x) as follows.

(1)

If n = 1 then compute the element f g of $\mathbb {R}$.

(2)

Define f = F₁ x^n/2 + F₀ and g = G₁ x^n/2 + G₀ where F₁, F₀, G₁, G₀ have degree < n/2.

(3)

Compute F₀ G₀, F₁ G₁, (F₀ + F₁)(G₀ + G₁) recursively

(4)

Return

$$\left(\vphantom{ (F_0 + F_1)(G_0 + G_1) - F_0 \, G_0 - F_1 \, G_1 }\right. \left.\vphantom{ (F_0 + F_1)(G_0 + G_1) - F_0 \, G_0 - F_1 \, G_1 }\right)$$ (47)

ITS COMPLEXITY. Let us count how many operations in $\mathbb {R}$ we perform with the Karatsuba's trick.

• At step (3) we perform at most n additions to compute (F₀ + F₁) and (G₀ + G₁).
• At step (4) we perform at most 2 n subtractions to compute (F₀ + F₁)(G₀ + G₁) - F₀ G₀ - F₁ G₁
• At step (5) we perform at most n additions to add this latter polynomial to F₁G₁ xⁿ + F₀ G₀.

Hence we can apply the previous formula (for estimating T(n)) with

$$\left\{\vphantom{ \begin{array}{rcl} a & = & 3 \\ T(1) & = & 1 \\ S(n) & = & 4 \, n \end{array} }\right. \begin{array}{rcl} a & = & 3 \\ T(1) & = & 1 \\ S(n) & = & 4 \, n \end{array}$$ (48)

We obtain

$$\in \cal {O}$$ (49)

that is

$$\in \cal {O}$$ (50)

Observe that:

$$\leq$$ (51)

Figure 5: Complexity of the Karatsuba algorithm.