Talk:Rader's FFT algorithm: Difference between revisions

Revision as of 17:53, 24 October 2017

Latest revision as of 10:35, 23 May 2024

(9 intermediate revisions by 7 users not shown)

Line 1:

{{WikiProject banner shell|class=Start|

{{WikiProject Computing |importance=Low |science=y |science-importance=Low |software=y |software-importance=Low}}

{{WikiProject Mathematics|priority=Low }}

}}

Hey, does anyone have a ___location for where this conference took place. The citation reads:

Line 11 ⟶ 15:

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? [[Special:Contributions/2A02:8109:9340:112C:FD62:EAA0:5CCE:62F8|2A02:8109:9340:112C:FD62:EAA0:5CCE:62F8]] ([[User talk: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.<ref> (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).</ref>) I'll add a link. (It's also discussed in [[Primitive root modulo n#Finding primitive roots]].) [[User:Stevenj|— Steven G. Johnson]] ([[User talk:Stevenj|talk]]) 18:03, 24 October 2017 (UTC)

== So who is "Rader"? ==

Line 18 ⟶ 22:

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

== 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? <!-- Template:Unsigned --><span class="autosigned" style="font-size:85%;">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Raysphere24|Raysphere24]] ([[User talk:Raysphere24#top|talk]] • [[Special:Contributions/Raysphere24|contribs]]) 08:18, 3 January 2021 (UTC)</span> <!--Autosigned by SineBot-->

:Agree. [[Special:Contributions/128.54.13.249|128.54.13.249]] ([[User talk:128.54.13.249|talk]]) 22:14, 9 November 2023 (UTC)

:Agree as well. I see no O(n²⁾ runtime. [[Special:Contributions/2A02:1210:2657:D600:63B7:3ED2:BBA4:60D3|2A02:1210:2657:D600:63B7:3ED2:BBA4:60D3]] ([[User talk:2A02:1210:2657:D600:63B7:3ED2:BBA4:60D3|talk]]) 10:35, 23 May 2024 (UTC)