FFT
Wikipedia
En snabb Fouriertransform, på engelska fast Fourier transform (FFT), är en effektiv algoritm för att beräkna en diskret, tidsbegränsad Fourier-transform (DTFT). Vanligtvis kräver en DTFT av en signal med N sampelpunkter N2 multiplikationer, men med hjälp av FFT sjunker denna siffra till i storleksordningen NlogN multiplikationer.
Den första matematikern som använde FFT, 160 år före sina kollegor, var Gauss runt 1805 men som så mycket annat p.g.a. sin stora pedantism så publicerade han inte sina resultat vilket medförde att den föll i glömska tills den återupptäcktes av J. W. Cooley och J. W. Tukey 1965.