Wraparound multiplicaton vs mullo

[Niels Möller]

David Harvey <dmharvey at cims.nyu.edu> writes:

> I haven't thought about this very carefully yet, but my guess is that
> the "FFT" algorithm you have in mind, i.e. mimicking the sequence of
> butterflies in a genuine FFT, is not really evaluating the input
> polynomial at 1, w, ..., w^(2^k - 1). You might want to check this
> for k = 2 or something.

This is what I get:

Assume that w is a primitive nth root (n a power of two). Inputs are
x_k, interpreted as a polynomial

  f(s) = \sum_{k = 0}^{n-1} x_k s^k

Define the transform y_j by

  y_j = f(w^j) = \sum_{k = 0}^{n-1} x_k w^{jk}
               = \sum_{k = 0}^{n/2-1} (x_k + w^{j n/2} x_{k+n/2}) w^{jk}

Now consider even elements, j = 2i. since 2i n/2 = 0 (mod n) we get

  y_{2i} = \sum_{k = 0}^{n/2-1} (x_k + w^{2i n/2} x_{k+n/2}) w^{2ik}
         = \sum_{k = 0}^{n/2-1} (x_k + x_{k+n/2}) (w^2)^ik

And for odd j, j = 2i + 1, we have (2i + 1) n/2 = n/2 (mod n) which implies

  y_{2i+1} = \sum_{k = 0}^{n/2-1} (x_k + w^{n/2} x_{k+n/2}) w^{(2i+1) k}
           = \sum_{k = 0}^{n/2-1} w^k (x_k + w^{n/2} x_{k+n/2}) (w^2)^{ik}

The even and odd parts correspond to the "generalized butterfly"

  y0 = x0 + x1
  y1 = w^k (x0 + w^{n/2} x1)

in the first stage of the FFT.

And of course, in the usual case, w^{n/2} reduces to -1 and the
"standard" butterfly operation.

/Niels