The Karatsuba trick

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

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

and

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

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

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

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

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

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

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

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

(1) mathend000#

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

(2) mathend000#

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

(3) mathend000#

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

(4) mathend000#

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)$$ (41)

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

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

Hence we can apply the previous formula (for estimating T(n) mathend000#) 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}$$ (42)

We obtain

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

that is

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

Observe that:

$$\leq$$ (45)

Figure 5: Complexity of the Karatsuba algorithm.