Fast Fourier Transform: Difference between revisions

Revision as of 21:22, 2 September 2006

Fast Fourier Transform is an efficient algorithm for calculating the discrete fourier transform (DFT). Reduces the execution time by hundreds in some cases. Whereas DFT takes an order of $O(n^{2})\,$ computations, FFT takes an order of $O(n\,\log \,n)$ , and is definitely the preferred algorithm to used in all applications. The FFT in most implementations consistent of samples that are exactly a power of 2.

Revision as of 07:59, 2 September 2006 (view source) Pepoluan (talk \| contribs) (<math>-ify the expressions) ← Older edit		Revision as of 21:22, 2 September 2006 (view source) HotshotGG (talk \| contribs) m (... that's not true. Most FFT algorithms are power 2 based, however there can be mixed radix implementations ;-D) Newer edit →
Line 1:		Line 1:
	Fast Fourier Transform is an efficient algorithm for calculating the discrete fourier transform ([[DFT]]). Reduces the execution time by hundreds in some cases. Whereas [[DFT]] takes an order of <math>O(n^2)\,</math> computations, FFT takes an order of <math>O(n\,\log\,n)</math>, and is definitely the preferred algorithm to used in all applications. The ~~disadvantage of the~~ FFT ~~is that the number~~ of samples ~~must be~~ exactly a power of 2.		Fast Fourier Transform is an efficient algorithm for calculating the discrete fourier transform ([[DFT]]). Reduces the execution time by hundreds in some cases. Whereas [[DFT]] takes an order of <math>O(n^2)\,</math> computations, FFT takes an order of <math>O(n\,\log\,n)</math>, and is definitely the preferred algorithm to used in all applications. The FFT in most implementations consistent of samples that are exactly a power of 2.


	[[Category:~~Technical~~]]		[[Category:Algorithms]]