Talk:Rader's FFT algorithm
Hey, does anyone have a location for where this conference took place. The citation reads:
C. M. Rader, "Discrete Fourier transforms when the number of data samples is prime," Proc. IEEE 56, 1107–1108 (1968)
but I don't see a location.
- Proceedings of the IEEE is a journal, not a conference. See here. —Steven G. Johnson 21:54, 2 April 2007 (UTC)
Finding the generator (g)
The algorithm explained in the article uses a generator - g - of the modulo N multiplication group, known to exist from number theory. However, no algorithmic way is mentioned to find such a generator. Is there an efficient way to do this? 2A02:8109:9340:112C:FD62:EAA0:5CCE:62F8 (talk) 01:01, 9 February 2015 (UTC)
- Since the generators are extremely common, just exhaustive testing will turn one up pretty quickly, although there are slightly faster algorithms than this. (See e.g. Donald E. Knuth, The Art of Computer Programming, vol. 2: Seminumerical Algorithms, 3rd edition, section 4.5.4, p. 391 (Addison–Wesley, 1998).) I'll add a link. (It's also discussed in Primitive root modulo n#Finding primitive roots.) — Steven G. Johnson (talk) 18:03, 24 October 2017 (UTC)