Wraparound multiplicaton vs mullo
Niels Möller
nisse at lysator.liu.se
Thu Oct 15 17:19:42 CEST 2009
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
More information about the gmp-devel
mailing list