FAST FOURIER TRANSFORM
473
Complex Roots of Unity
It turns out that the most convenient points to use for polynomial interpolation
and evaluation are complex numbers, in fact, a particular set of complex
numbers called the complex roots of unity.
A brief review of some facts about complex analysis is necessary. The
number i = is an imaginary number: though is meaningless as
a real number, it is convenient to give it. a name, i, and perform algebraic
manipulations with it, replacing with -1 whenever it appears. A complex
number consists of two parts, real and imaginary, usually written as a bi,
where a and b are reals. To multiply complex numbers, apply the usual rules,
but replace with -1 whenever it appears. For example,
+ bi)(c + di) = (ac bd) + (ad + bc)i.
Sometimes the real or imaginary part can cancel out when a complex multi-
plication is performed. For example,
(1 i)(l =
(1 = -4,
(1 + = 16.
Scaling this last equation by dividing through by 16 = we find that
In general, there are many complex numbers that evaluate to 1 when raised
to a power. These are the so-called complex roots of unity. In fact, it turns
out that for each there are exactly N complex numbers with = 1.
One of these, named is called the principal Nth root of unity; the others
are obtained by raising to the kth power, for = . . ,N 1. For
example, we can list the eighth roots of unity as follows:
The first root,
is 1 and the second, is the principal root. Also, for
N even, the root is -1 (because = 1).
The precise values of the roots are unimportant for the moment. We’ll be
using only simple properties which can easily be derived from the basic fact

on points (the roots of unity) to compute the values needed for the
full evaluation.
To see this more clearly, consider the evaluation of a degree-7 polynomial
p(x) on the eighth roots of unity
Since = -1, this is the same as the sequence
:
Squaring each term of this sequence gives two copies of the sequence of
the fourth roots of unity:
THE FAST
475
Now, our equation
tells us immediately how to evaluate at the eighth roots of unity from
these sequences. First, we evaluate and at the fourth roots of unity.
Then we substitute each of the eighth roots of unity for x in the equation
above, which requires adding the appropriate value to the product of the
appropriate value and the eighth root of unity:
=
= +
= +
= +
=
=
=
=
In general, to evaluate p(x) on the Nth roots of unity, we recursively evaluate
p,(x) and on the roots of unity and perform the N multiplications
as above. This only works when N is even, so we’ll assume from now on that
N is a power of two, so that it remains even throughout the recursion. The
recursion stops when N = 2 and we have to be evaluated at 1 and
-1, with the results + and -pi.

tion problem. When the points under consideration are the complex roots of
unity, this is literally true. If we let
then we can get the coefficients
just by evaluating the polynomial s(x) at the inverses of the complex roots of
unity

8 8 8
which is the same sequence as the complex roots of unity, but in a different
order:

8'
In other words, we can use exactly the same routine for interpolation as
for evaluation: only a simple rearrangement of the points to be evaluated is
required.
The proof of this fact requires some elementary manipulations with finite
sums: those unfamiliar with such manipulations may wish to skip to the end
of this paragraph. Evaluating at the inverse of the tth Nth root of unity
FAST FOURLER TRANSFORM 477
gives
=
= Nearly everything disappears in the last term because the inner sum is trivially
N if i = t: if i t then it evaluates to

j(i-t) N

Note that an extra scaling factor of N arises. This is the “inversion theorem”
for the discrete Fourier transform, which says that the same method will