Fast Fourier transform: verschil tussen versies

In zijn eerste vorm, als ontwikkeld door [[James Cooley]] en [[John Tukey]], kon de FFT inderdaad alleen gebruikt worden als het aantal punten een macht van 2 was. Later is dit gegeneraliseerd naar andere [[priemfactor]]en, waardoor een meer algemene toepasbaarheid ontstond. Als het aantal punten een grote priemfactor heeft kan dit echter zeer nadelige gevolgen hebben voor de rekentijd. Voor praktische toepassing zoals in [[signaalanalyse]] heeft de beperking tot machten van twee nauwelijks gevolgen. Wanneer een 3-dimensionale FFT wordt gebruikt, zoals in de [[kristallografie]], kan het echter leiden tot bijna 8 keer meer geheugengebruik en 24 keer meer rekentijd dan strikt noodzakelijk.

 

 

[[Categorie:Algoritme]]