Content deleted Content added
| (10 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 10 ⟶ 14:
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. (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]].) [[User:Stevenj|— Steven G. Johnson]] ([[User talk:Stevenj|talk]]) 18:03, 24 October 2017 (UTC)
== So who is "Rader"? ==
Line 16 ⟶ 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<sup>2</sup>) 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%;">— 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<sup>2)</sup> 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)
| |||