I've been looking everywhere for a sample Fast Fourier Transform implementation/tutorial in (preferably) C#.
However, every one I've found has been poor at explaining what's going on, and/or poorly commented; or they assume that you already know the FFT algorithm, or they're tutorials about how to USE FFTs.
Anyone know of a good sample/tutorial?
Google turns up a few:
FFTW (C library DLL that can be called from C#)
The FFTW library is recommended as a solution fast FFTs.
Here is another one written in C.
http://www.archelon.com/fft.html
Also, can you make your question more specific. For example, do you want to compare the DFT to the FFT? Are you interested in why the FFT is so much faster?
If I remember correctly DFT is something like N^2 multiplications and the FFT is about N log N multiplications, where N is number of samples in the signal.
Wikipedia has a great writeup of the FFT: http://en.wikipedia.org/wiki/Fft.
As far as implementations go, FFTW is the fastest I've ever used, but the code is extremely difficult to understand as it is crazy optimized. There are tons of links to basic FFT implementations, including plenty in C#; Google is your friend here.
http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html (yeesh, i found this useful but the font and layout are horrible. i hope it's just my browser being weird)
The old standard book for number crunching: Numerical Recipes, may have an sufficient explanation.
If you can find a copy, Musical Applications of Microprocessors by Hal Chamberlin, 1983 (?) may have a section of FFT - alas my copy is at work right now so i can't check the book specifically for FFT wisdom. But i did learn many basics of audio filtering, sampling etc. and there is plenty of material on Fourier transforms and their uses.
Apologies for lack of hyperlinks, I do not have permissions to add them :(
You are asking for two things here
1) An explanation of the FFT
Very briefly:
If you want to obtain the frequency domain representation of a signal you use the fourier transform, this is a mathematical transform which transforms a signal from the time domain to the frequency domain. When operating on digital signals we have a set of discrete samples so we must use the Discrete Fourier Transform or DFT. However this is a rather slow operation and is easily optimised, so we instead use a Fast Fourier Transform algorithm or FFT.
This is a large signal processing topic so I suggest you look for a signal processing book to use as a reference. I suggest "Digital Signal Processing: A Practical Approach". There is of course the ubiquitous wikipedia article as well.
2) An implementation of the FFT
Because of the highly optimised nature of the FFT platforms and languages often have specific implementations, you should check headers and documentation (typically it will be found in an 'audio' section) in case it is included in a standard library.
If you want to implement the algorithm yourself I recommend finding a copy of Numerical Recipes, this contains an entire chapter on the FFT, as well as a chapter on "Fourier and Spectral Applications". There is well documented pseudocode which should be easy to transcribe into any language.
For a third party solution a popular choice is FFTW, a C library. I google search for "FFT Library" will provide you with some alternatives.
See kissfft on sourceforge. It lacks a bit of the speed of FFTW, but makes up for it in small size and readability. There is a pdf also on sourceforge about the derivation -- required if you are going to try to understand it.