Talk:Rader's FFT algorithm

Computing: Software / CompSci Start‑class Low‑importance

This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing

Start

This article has been rated as Start-class on Wikipedia's content assessment scale.

Low

This article has been rated as Low-importance on the project's importance scale.

This article is supported by WikiProject Software (assessed as Low-importance).

This article is supported by WikiProject Computer science (assessed as Low-importance).

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Mathematics Start‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

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)[reply]

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)[reply]

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)[reply]

So who is "Rader"?

This article isn't very clear who the "Rader" in question is. If it's Rader's FFT algorithm, then it should say who it was named after.--Varkman (talk) 05:16, 20 November 2015 (UTC)[reply]

Note that this has been fixed (it is Charles M. Rader, a well-known figure in the signal-processing community). — Steven G. Johnson (talk) 17:52, 24 October 2017 (UTC)[reply]

Time complexity without zero-padding

Without zero-padding, the article states that the worst case requires O(N²) time. But each step of the recursion halves N, therefore isn't it still O(N log N) time?