can't be changed

Fixed misspelling - "Cooley-Turkey" -> "Cooley-Tukey"

@dvbuntu,

First of all, thanks for trying out my Kata.

With regards to the FFT algorithm(s) required to pass this Kata, the description states that any FFT algorithm that passes all tests and doesn't time out is acceptable. FYI even the reference solution only passes the Kata about 50% of the time so if you've implemented your radix-2 FFT correctly, you might be able to submit after a few more attempts.

That being said, it is not the intention of this Kata for you to pad the input with zeroes to the next power of two although you could do that if the results returned still fall within the 1e-6 relative error range. To give you an idea of the approach expected, the reference solution uses a mixed-radix Cooley-Tukey (thanks for correcting me ;) algorithm by means of prime factorization so it should have a speed advantage over your implementation for most odd inputs (provided said number is not prime). I'll leave you to figure out how to implement such a mixed-radix approach (no, you can't find the exact equations on Wikipedia; I had to derive them myself when I authored this Kata) ;)

As for the name of the algorithm, I just checked and it appears that you're correct, not sure how I got that wrong in the first place :p

Cheers,
@donaldsebleung

P.S. If you're feeling ambitious, you could also try to incorporate other FFT algorithms to specifically deal with prime-length input but I personally couldn't be bothered to investigate it myself :p

Maybe allocating a dynamic string like "str"?

I like uppercase style...:-)

I didn't know that because the test was passed. Thanks.