Next: Experimentation Up: Asymptotically fast algorithms Previous: Asymptotically fast algorithms

## The Karatsuba trick

Let f, g be two univariate polynomials in x with degrees p and q respectively. Let be their ring of coefficients. Define

 f (x)  =   apxp + ... + a1x + a0 (45)

and

 g(x)  =   bqxq + ... + b1x + b0. (46)

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

• (p + 1)(q + 1) multiplications in and
So the complexity of this computation is (pq) (in term of operations in ).

Thus the complexity of the computation of the product of two univariate polynomials of degree at most n is (n2) (in term of operations in ).

COMPUTING THE SUM f (x) + g(x) is (n) (in term of operations in ) 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 addition is also cheaper than multiplication. So when computing f (x)g(x) let's try to save on the number of multiplications in .

THE KARATSUBA'S TRICK. Assume f and g have degree (strictly) less than n = 2k (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 .
(2)
Define f = F1 xn/2 + F0 and g = G1 xn/2 + G0 where F1, F0, G1, G0 have degree < n/2.
(3)
Compute F0 G0, F1 G1, (F0 + F1)(G0 + G1) recursively
(4)
Return

 F1G1 xn + (F0 + F1)(G0 + G1) - F0 G0 - F1 G1xn/2 + F0 G0. (47)

ITS COMPLEXITY. Let us count how many operations in we perform with the Karatsuba's trick.

• At step (3) we perform at most n additions to compute (F0 + F1) and (G0 + G1).
• At step (4) we perform at most 2 n subtractions to compute (F0 + F1)(G0 + G1) - F0 G0 - F1 G1
• At step (5) we perform at most n additions to add this latter polynomial to F1G1 xn + F0 G0.
Hence we can apply the previous formula (for estimating T(n)) with

 (48)

We obtain

 T(n) (4 n nlog2(3)-1). (49)

that is

 T(n) (nlog2(3)). (50)

Observe that:

 log2(3) 1, 59. (51)

Subsections

Next: Experimentation Up: Asymptotically fast algorithms Previous: Asymptotically fast algorithms
Marc Moreno Maza
2003-06-06