We first change the intermediate polynomials.
Let
be a power of
, let
be a primitive
-th
root of unity and
.
We define
|
(55) |
such that we have
|
(56) |
Hence evaluating
at
is reduced to evaluate
and
at
.
But this second sequence of powers of
consists
of two identical sequences of length
.
Indeed, for every integer
we have
|
(57) |
Since
holds, we obtain
|
(58) |
Hence we only need to evaluate
and
at
|
(59) |
This provides us directly with the values of
at
|
(60) |
and the values of
at
|
(61) |
by using the fact these numbers are respectively equal to
|
(62) |
To summarize, for
we have
|
(63) |
Algorithm 3
The validity of Algorithm 3
follows from the two following observations.
- Formulas (63).
- If
is a primitive
-root of unity, with
,
then
is a primitive
-root of unity.
Observe that the recursive calls of
defines
an ordering of the coefficients of
shown
on Figure 2 for
.
Let us call this ordering the DFT ordering of
.
Observe that if the input array
is sorted w.r.t. this
DFT ordering, one can describe easily the
recursive calls with a binary tree.
If this tree is traversed bottom-up, from left to right,
we are led to an iterative algorithm working in place!
For instance, for
, assuming that the input array
is
We obtain the desired result in
using the following straigth-line program
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
-
:=
Figure 2:
Recursive calls for
.
|
Algorithm 4
Remark 8
To get the DFT ordering for
,
that is
,
observe that this ordering changes
|
(64) |
to
|
(65) |
Remark 9
The ring
does not have any interesting roots of unity.
In order to take advantage of the FFT-based multiplication
one could use a modular approach as follows.
Marc Moreno Maza
2008-01-07