4.1 CALCULATING POLYNOMIALS 109into two polynomials of lesser degree. For example, if you want to calculate
x^256 , you could use a loop like the one in the function Evaluate at the start
of this section and do 255 multiplications. An alternative would be to set
result = x x and then do the statement result = result result
three times. We get the same answer with just four multiplications. After the
first, result will hold x^4. After the second, it will hold x^16 , and after the third,
it will hold x^256.
For preprocessed coefficients to work, we need our polynomial to be monic
(an = 1) and to have its largest degree equal to 1 less than a power of 2 (n = 2k
1 for some k = 1).^1 If this is the case, we can factor the polynomial so that
p(x) = (xj + b)*q(x) + r(x) where j = 2k^1 (4.3)There will be half as many terms in q(x) and r(x) as in p(x). To get the results
we want, we would evaluate q(x) and r(x) and then do one additional multipli-
cation and two additions. The interesting thing about this process is that if we
choose the value of b carefully, both q(x) and r(x) will be monic polynomials
with the proper degree for this process to be applied again. After all of this is
done, we will see that this process does save calculations.
Instead of looking at just generic polynomials, consider the following:
p(x) = x^7 + 4x^6 8 x^4 + 6x^3 + 9x^2 + 2x 3
We first need to determine the value of (xj + b) for Equation 4.3. Looking at
p(x) we see that its largest degree is 7, which is 2^3 1, so that means k is 3.
This makes j =2^2 = 4. We choose a value of b so that both of the equations,
q(x) and r(x), are monic. To achieve that, we need to look at the coefficient of
thej 1 term in the equation and make b = aj 1 1. For our above equation,
this means that b will have the value of a 3 1, or 5. We now need to find the
values of q(x) and r(x) that satisfy the equation
x^7 + 4x^6 8 x^4 + 6x^3 + 9x^2 + 2x 3 = (x^4 + 5) *q(x) + r(x)(^1) The savings of this method can be large enough that it is sometimes faster to add the
terms necessary to be able to use this method and then subtract those values from the
result returned. In other words, if we had an equation with degree 30, we would add
x^31 , determine the factorization, and then subtract x^31 from every answer. This would
still save time over using another method for the calculation.