Problem 1509. Fast Fourier transform algorithm

Created by Bob Levy

Solve Later

Your task is to implement the Fast Fourier transform algorithm, without using builtin MATLAB fft commands e.g. fft, fft2, or hardcoded numeric answers in the test case. The test suite employs regular expression matching to reject such solutions.
Creative hacking attempts are appreciated. While I will update the test case accordingly, I'll send you some MathWorks swag if you're the first to demonstrate a new way to get the Test Suite to pass (maybe a t-shirt or coffee mug, you'll have to try and see :-) Jose', yours is on the way.
reference: http://en.wikipedia.org/wiki/Fast_Fourier_transform

Solve

Solution Stats

481 Solutions
14 Solvers

Last Solution submitted on Sep 03, 2024

Last 200 Solutions

Problem Comments

3 Comments

3 Comments

Selvaraaju Murugesan on 15 May 2013

Some numerical inaccuracies with the test case and the expected output!

G K on 15 May 2013

float tolerance needed ?

Peter Cook on 2 Oct 2014

I'm off by O(10*eps) from the test suite, can you possibly test isequal(single(fft(x)),single(y))

Solution Comments

Show comments

Problem Recent Solvers14

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!