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_p x^p + \cdots + a_1 x + a_0$$ (39)

and

$$g(x) \ \ = \ \ b_q x^q + \cdots + b_1 x + b_0.$$ (40)

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

• $(p + 1) (q + 1)$ multiplications in ${\mathbb{R}}$ and
• $p q$ 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^2)$ (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_1 \, x^{n/2} + F_0$ and $g = G_1 \, x^{n/2} + G_0$ where $F_1, F_0, G_1, G_0$ have degree $< n/2$ .

$(3)$

Compute $F_0 \, G_0$ , $F_1 \, G_1$ , $(F_0 + F_1)(G_0 + G_1)$ recursively

$(4)$

Return

$$F_1 G_1 \, x^n + \left( (F_0 + F_1)(G_0 + G_1) - F_0 \, G_0 - F_1 \, G_1 \right) x^{n/2} + F_0 \, G_0.$$ (41)

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_0 + F_1)$ and $(G_0 + G_1)$ .
• At step $(4)$ we perform at most $2 \, n$ subtractions to compute $(F_0 + F_1)(G_0 + G_1) - F_0 \, G_0 - F_1 \, G_1$
• At step $(5)$ we perform at most $n$ additions to add this latter polynomial to $F_1 G_1 \, x^n + F_0 \, G_0$ .

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

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

We obtain

$$T(n) \in {\cal O} (4 \, n \, n^{{{\log}_2}(3) - 1}).$$ (43)

that is

$$T(n) \in {\cal O} (n^{{{\log}_2}(3)}).$$ (44)

Observe that:

$${{\log}_2}(3) \leq 1,59.$$ (45)

Figure 5: Complexity of the Karatsuba algorithm.