View License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
Sprint Race for Fast Butterflies

  • dif_fft(x)Radix-2, Decimation in Frequency (DIF) FFT Computation.
  • fft_it(x)This custom function is an iterative implementation of the
  • fft_it2(x)This custom function is an iterative implementation of the
  • fft_rec(x)This custom function is a recursive implementation of the
  • ger_fft(x)German Style Decimation-In-Time (DIT) radix-2 FFT.
  • ger_fft2(x)German-Style Decimation-In-Time (DIT) radix-2 FFT.
  • radix2fft(x)Radix-2, Decimation-In-Time (DIT), FFT Computation function.
  • radix4fft(x)Radix-4, Decimation-In-Time (DIT), FFT Computation function.
  • splitradixfft(x)Split-Radix, Decimation-In-Time (DIT), FFT Computation function.
  • bench_fft.mFFT benchmark.
  • View all files
Be the first to rate this file! 5 Downloads (last 30 days) File Size: 21.4 KB File ID: #40097 Version: 1.1
image thumbnail

Sprint Race for Fast Butterflies



30 Jan 2013 (Updated )

Benchmarking of Various FFT Algorithm Implementations Based on Execution Time.

| Watch this File

File Information

The following FFT implementations are provided: 1) Radix-2 DIT Recurcive FFT, 2) In Place Radix-2 DIT Iterative FFT, 3) Radix-2 DIT FFT, 4) Radix-4 DIT FFT, 5) Radix-2 DIT Iterative mex-coded FFT, 6) Split-Radix DIT FFT, 7) Radix-2 DIF FFT. DIT = Decimation In Time, DIF = Decimation In Frequency.

Required Products MATLAB
MATLAB release MATLAB 8.0 (R2012b)
MATLAB Search Path
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (3)
06 Jan 2016 M. Welters

Hi Ilias, thank you for sharing your nice work!
Decades ago I coded my own iterative FFT function in Turbo Pascal. As far as I remember I got a very high speed boost by taking the "twiddle factors" from a pre-calculated look-up table instead of calculating them again and again like exp(-2*pi*1i/N) .^ (0:m-1) in your fft_rec.m.
Would you like to try this potential improvement too?

Comment only
01 Feb 2013 Ilias Konsoulas

To Mikhail: Yes. The script fft_it2.m is used to generate fft_it2_mex via MatLab's codegen. The procedure is described at the bottom of file fft_it2.m. As can be seen the coding in files fft_it.m and fft_it2.m are identical. The purpose of this "dual" effort is to demonstrate the acceleration obtained via mex coded functions.

Comment only
01 Feb 2013 Mikhail

Mikhail (view profile)

Hi! Are you using fft_it2_mex instead of fft_it2 by intention in your bench_fft.m?

Comment only
31 Jan 2013 1.1

I have only modified the title of this submission.

07 Oct 2016 1.1

I have improved dif_fft.m and rec_fft.m by killing some unneeded for loops. I also have included an FFT implementation (both in matlab and mex-coded) found in "Numerische Mathematik kompakt" by Robert Plato.

Contact us