Fast Fourier Transform
De FFT (Fast Fourier Transform) is een algoritme waarmee een (discrete) Fourier transformatie van een signaal (array) met N punten uitgerekend kan worden met een efficiëntie van O(NlogN). De recht-toe-rechtaan berekening van de Fourier Transformatie levert een O(N2) algoritme op. De tijdwinst die hiermee gemoeid kan zijn is voor grote N dramatisch.
Het algoritme komt er in kort bestek op neer dat een Fourier transformatie met lengte N wordt gesplitst in twee transformaties met lengte N/2. Door deze opsplitsing met recursie toe te passen ontstaat een verbetering van N/log2N. Voor N=8192 is dat al een factor 630...
Een zo toegepaste recursie impliceert een lengte die altijd een macht van 2 is. In zijn eerste vorm, als ontwikkeld door Cooley en Tukey, kon de FFT inderdaad alleen gebruikt worden als het aantal punten een macht van 2 was. Later is dit gegeneraliseerd naar andere priemfactoren, 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 'alleen-machten-van-twee- beperking' 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.
zie ook Fourier analyse
