0

I'm a bit of a novice when it comes to implementing FFTs in general, but I have most of the basic ideas down I think. In this specific case, I've an implementation of the number theoretic transform on the 257 finite field. It's basically your typical Radix-2 Cooley-Tukey FFT. What Id like to know is either: is there a good alternative to the Cooley-Tukey Radix-2 that's better suited to doing this particular NTT efficiently (if the answer is an unqualified yes or a yes conditional on something not entirely within the scope of this question, I'm interested in hearing about either), or are there things specific to a Mersenne NTT that allow for a more efficient implementation than a more general case?

MNagy
  • 423
  • 7
  • 20

1 Answers1

0

I'd say that for dyadic length FFT there is nothing better than Cooley-Tukey.

This has nothing directly to to with Mersenne numbers, any number field with modulus 2^(m*2^n)+1 qualifies. I=2^(m*2^(n-1)) is the complex unit, I^2=2^(m*2^n)=-1 mod (2^(m*2^n)+1), and q=2^(2*m) is a primitive 2^n-th root of unity.

For inspiration for the second point see Section 1 of Schönhage: Asymtotically fast algorithms for the numerical multiplication ..., with overall summary of fast multiplications

Lutz Lehmann
  • 25,219
  • 2
  • 22
  • 51
  • It's been a while, but I keep coming back to this question. You've said that "for dyadic length FFT there is nothing better than Cooley-Tukey"... why is that/what should I read in order to understand why this is? – MNagy Apr 17 '15 at 19:35
  • DFT and its inverse is a special case of multi-point evaluation and interpolation. The best known algorithms for that are O(n*log(n)) (essentially, omitting additional loglog factors). Cooley-Tukey has the smallest factor in that complexity estimate. The only point to optimize is to chose when to cut off and "unroll" the recursion, at length 16, 8 or 4. – Lutz Lehmann Apr 18 '15 at 14:30
  • That's useful to know; do you know of a good source to read that does some explicit comparisons between Cooley-Tukey and, perhaps, Bruun's and Rader's FFT algorithms (and any others of significance)? – MNagy Apr 18 '15 at 17:56