3-prime FFT

[Torbjorn Granlund]

Guillermo Ballester Valor <gbv@oxixares.com> writes:

  I'm thinking that because for 64-bit machines and two primes,
  we can achieve big basecases with big FFT runlengh. In a 32-bit
  case it is not true.
  
I am afraid I don't understand this.

  Then the CRT is more complicated than in the two-prime case,
  and also don't forget we also need to do three FFT-based mul
  instead of two although the small prime one were a lot faster.

We just need O(n) CRT operations, so that isn't the biggest
problem.  But we should almost surely use just two primes for
operands, at least under a certain size.


  Hum, for so small size (16 bits) it would be hard to find
  primes with the propierties one usally wants (I'm thinkinig in
  triplet/pair of primes p such as p-1 is divisible by k*2^j, k
  usually a small prime 3,5 or 7 for non_power_of_two FFTS).

0xA001 with primitive root 3 would allow transform sizes up to
2^13.

But the more I think about it, the more I suspect we want to use
just two primes, and then as large as possible.
  
-- 
Torbjörn