Problem 1509. Fast Fourier transform algorithm

Created by Bob Levy

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>reference:</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Fast_Fourier_transform\"><w:r><w:t>http://en.wikipedia.org/wiki/Fast_Fourier_transform</w:t></w:r></w:hyperlink></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

77 Solutions
10 Solvers

Last Solution submitted on Oct 05, 2016

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

Solution 280284

2 Comments

2 Comments

Jean-Marie Sainthillier on 14 Jul 2013

I don't know why regexp miss this ...

J.R.! Menzinger on 20 Aug 2013

Very Nice solution!!

hehehe

Solution 244790

3 Comments

3 Comments

J.R.! Menzinger on 15 May 2013

Ok! a little hack on this... ;-)

Bob Levy on 14 Jun 2013

Jose', you've inspired me to make this a bit of a hacking competition. I'll update the test suite to address issues found, but will reward the first to find issues like you have by sending MathWorks swag (maybe a t-shirt or coffee mug, you'll have to try and see :-) Jose', yours is on the way.

J.R.! Menzinger on 9 Jul 2013

I became my t-shirt and my basecap with the post for 3 days... THANK YOU!! ;-)

Problem Recent Solvers10

Problem Tags

algorithms

Community Treasure Hunt

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

Start Hunting!