Let f, g be two univariate polynomials in x with degrees p and q respectively. Let be their ring of coefficients. Define
f (x) = a_{p}x^{p} + ^{ ... } + a_{1}x + a_{0} | (45) |
g(x) = b_{q}x^{q} + ^{ ... } + b_{1}x + b_{0}. | (46) |
COMPUTING THE PRODUCT f (x)g(x) by the straightforward method requires
Thus the complexity of the computation of the product of two univariate polynomials of degree at most n is (n^{2}) (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 = 2^{k} (where k is an integer). The Karatsuba's trick computes the product f (x)g(x) as follows.
F_{1}G_{1} x^{n} + (F_{0} + F_{1})(G_{0} + G_{1}) - F_{0} G_{0} - F_{1} G_{1}x^{n/2} + F_{0} G_{0}. | (47) |
ITS COMPLEXITY. Let us count how many operations in we perform with the Karatsuba's trick.
(48) |
T(n) (4 n n^{log2(3)-1}). | (49) |
T(n) (n^{log2(3)}). | (50) |
log_{2}(3) 1, 59. | (51) |