Th desire to apply the trick of using positive and negative pairs recursively,
leads us to a very special set of points, called the Roots of Unity.
Recall that our goal is to compute two values of a polynomial for
the price of one, by dividing the terms up into even and odd powers.
>From here on,
we will assume that the number of points is equal to the order of the polynomial.
And that this number is a power of 2.
In the context of polynomial multiplication,
N will be the power of 2, that is at least as great as the number of
coefficients of the product of the two polynomials.
And we will pad the coefficients of the polynomials being multiplied with
the zeros, as needed to make their number equal to N as well.
In order to be able to do this computation recursively,
we need the sequence X to have the following proprieties.
First, they should all be distinct, otherwise our efforts will be wasted,
and we wont have enough points to interpolate back to find
the coefficients.
We also need the points to be symmetric or
anti symmetric, depending on how you look at it.
That is to say, we want the point with index J
plus N over 2 to the negative of X of J, and lastly,
we want all these properties to apply to the squares of these numbers, so
that we can use this trick recursively again and again.
If your polynomials are over some unusual field,
then it may make sense to choose an unusual set of values for X.
For most applications however, the coefficients will be integers or
reals or complex numbers.
And the choice of X will be the complex roots of unity.
We define omega N to be e to the 2 pi i divided by N,
and we let Xj be omega of N raised to the jth power.
Let's visualize these points in the complex plane.
I'll do this for N equal to 8.
All the points have magnitude 1,
so they'll be arranged around the unit circle, and
the angle from the positive real axis, is given by the exponent here.
Thus, omega to the j, will be j Nths around the circle.
Let's confirm that all the desired properties hold.
Indeed, the points are unique.
j here is always less than N, so there's no wrap around the circle.
The symmetric property holds, because adding N over 2 to j has
the effect of increasing this angle by pi, or half the circle.
And so that's equivalent to negating and flipping over both axes as well.
The recursive property is the hardest to confirm.
Notice however, that for all the points that have odd powers
in the exponent here, squaring these numbers makes the exponent even.
Thus omega 3 when squared, becomes omega to the 6th.
Omega fifth when squared, will become omega to the 10th,
which wraps around and then becomes omega to the 2nd.
Moreover, each of the even powers here
is the square of exactly two other points.
Which points?
Well, just divide the exponent by 2.
That gives you one of them.
For example, omega to the 4th, well his square root is omega to the 2.
What's the other point?
Well it's on the opposite side of the circle, of course.
The additional N over 2 in the exponent, comes an additional N when we square it,
so it's just an extra trip around the circle, and it's the same place.
For, omega squared, half is omega to the 1st power, and
then the opposite side is omega to the 5th.
The result of all this, is that when we square these numbers,
the odd powers of omega go away, like so.
Once we're left with, only the even powers however, It doesn't make sense to
express these points in terms of omega sub eight anymore.
The factors of two in the numerator j and the denominator N cancel.
So we can just divide both by two.
And voila,
we end up with the fourth roots of unity, instead of the eighth roots.
And the same logic applies to all N, where N is a power of 2.
And that then, shows that all these key properties that we wanted for
X are true,
when we choose them to be the Nth roots of unity, where N is a power of 2.
It's worth noting here, how few of the properties of complex numbers
were necessary for the recursion we used.
In fact, there are a number of theoretic algorithms that use modular arithmetic,
and avoid the precision difficulties associated with working with
complex numbers.
At the end of the lesson,
you'll get a chance to implement one of those yourself.