Fast Fourier Transform: Forskelle mellem versioner
Content deleted Content added
mNo edit summary |
Tilføjelse af primfaktormetode. |
||
Linje 53:
Ved at benytte FFT reduceres antallet af beregninger af exponentialfuktionen til <math>\operatorname{log_2}(n)</math> og antallet af multiplikationer til <math>n \cdot \operatorname{log_2}(n)</math>.<br />
Hvis n eksempelvis er 1024, så reduceres antallet af trigonometriske beregninger og multiplikationer fra 1.048.576 til 10 og 10240, hhv. Alt andet lige reducerer det beregningstiden med mindst en faktor 100.<br />
=== Alternative metoder ===
Den her viste metode bygger på, at længden af serien reduceres ved at dele den lige over i to halvdele. Heraf kommer kravet om, at <i>n</i> skal være en potens af 2.
Der er senere udviklet metoder, hvor man udnytter [[primtal|primfaktoropløsning]] af <i>n</i>. Når <i>m</i> indgår som primfaktor i <i>n</i>, så kan serien opdeles i <i>m</i> mindre serier, som hver har længden <i>n / m</i>. Disse kan så igen opdeles, indtil længden af serierne selv bliver primtal.
==Se også==
| |||