Java Reference
In-Depth Information
logarithm of the sum is read off another logarithmic scale. The part normally con-
sidered expensive (taking logarithms and anti-logarithms) is cheap because it is a
physical part of the slide rule. Thus, the entire multiplication process can be done
cheaply via a reduction to addition. In the days before electronic calculators, slide
rules were routinely used by scientists and engineers to do basic calculations of this
nature.
Now consider the problem of multiplying polynomials. A vector a of n values
can uniquely represent a polynomial of degree n 1, expressed as
n1
X
a
i
x
i
:
P
a
(x) =
i=0
Alternatively, a polynomial can be uniquely represented by a list of its values at
n distinct points. Finding the value for a polynomial at a given point is called
evaluation. Finding the coefficients for the polynomial given the values at n points
is called interpolation.
To multiply two n 1-degree polynomials A and B normally takes (n
2
) co-
efficient multiplications. However, if we evaluate both polynomials (at the same
points), we can simply multiply the corresponding pairs of values to get the corre-
sponding values for polynomial AB.
Example16.5
Polynomial A: x
2
+ 1.
Polynomial B: 2x
2
x + 1.
Polynomial AB: 2x
4
x
3
+ 3x
2
x + 1.
When we multiply the evaluations of A and B at points 0, 1, and -1, we
get the following results.
AB(1)
=
(2)(4) = 8
AB(0)
=
(1)(1) = 1
AB(1)
=
(2)(2) = 4
These results are the same as when we evaluate polynomial AB at these
points.
Note that evaluating any polynomial at 0 is easy. If we evaluate at 1 and -
1, we can share a lot of the work between the two evaluations. But we would
need five points to nail down polynomial AB, since it is a degree-4 polynomial.
Fortunately, we can speed processing for any pair of values c and c. This seems
to indicate some promising ways to speed up the process of evaluating polynomials.
But, evaluating two points in roughly the same time as evaluating one point only
speeds the process by a constant factor.
Is there some way to generalized these
