I implemented a textbook FFT on the Arduino last night using regular floating point math. It’s not as slow as you would think. The arduino can do a 64 point FFT on a complex signal in only 25 ms. If you’re looking at a real signal, you can get the FFT in only 16 ms. That’s pretty good! You can do a 32 band spectrum analyzer that runs at 50 Hz without resorting to fixed point math or assembly language.
I threw together a quick and dirty color organ implemented with a 16 sample FFT. I’ll post a video shortly.