Wraparound multiplicaton vs mullo

[Paul Zimmermann]

> >> while
> >> 
> >>   w = 2^{j - k}      (j > k)
> >> 
> >> is suitable when computing mod 2^n - 1.
> >
> > no, you want a primitive root of unity, which requires w^(n/2) = -1,
> > and this is not the case here.
> 
> Thanks, that's the second time I forget that requirement!
> 
> Actually, I think the above w *is* a primitive nth root of unity, since
> it satisfies w^n = 1 and w^i != 1 for 1 <= i < n. But for FFT to
> really work, one needs in addition that w^{n/2} = -1.

yes sorry what you really need is a *principal* root of unity, as David said,
i.e., such that \sum_{i=0}^{n-1} w^{ij} = 0 for 0 < j < n (it seems there
is a typo on http://mathworld.wolfram.com/PrincipalRootofUnity.html, which
includes j = n).

The fact that w^{n/2} = -1 for n even is a consequence: for j=n/2 the above
sum equals n/2 * (1 + w^{n/2}).

> But when computing in Z_m where m is not a prime number, there are
> more than two square roots of 1 (there are two choices mod each odd
> prime factor of m, and these can be combined using CRT, to give (at
> least) 2^{number of odd prime factors} square roots. Not sure what
> happens if m is a prime power, though).
> 
> So Z_m works as a coefficient ring for FFT, with a suitable 2^k'th
> root, if either
> 
>   m = 2^{2^k} + 1
> 
> or
> 
>   m = a 2^k + 1,  and prime
> 
> Are there any other possibilities?

yes, any m = 2^{a 2^{k-1}} + 1 works, with w = 2^a and n = 2^k.
This is what Schönhage-Strassen's algorithm uses. However I don't see
how your second example works, i.e., what w you take.

> Just one more thing, before we conclude that mod 2^n + 1 arithmetic is
> indeed essential for large-coefficient FFT multiplication:
> 
> The reason w^{n/2} = -1 is needed is that we want a simple negation
> in the butterfly operations, we want it to look like
> 
>   y_0 = x_0 + x_1
>   y_1 = w^k (x_0 - x_1)

I'm not sure this is the main reason. The main reason is that we want that
one forward transform followed by one backward transform gives the identity,
up to a constant factor. This gives exactly the definition of principal root.

> But if w^{n/2} != -1, we get instead the more general butterfly
> operation
> 
>   y0 = x0 + x1
>   y1 = w^k (x0 + w^{n/2} x1)

we could live with that, no? Anyway principal root ==> w^{n/2} = -1.

> and in the case of 2^n-1 arithmetic and w = 2, this is
> 
>   y0 = x0 + x1
>   y1 = 2^k (x0 + 2^{n/2} x1)
> 
> Then multiplication by 2^{n/2} mod 2^n-1 is a rotation (or rather, a
> swap of high and low halves) rather than a negation, but it shouldn't
> cost more than a negation.

Paul