Noting a distinct lack of decent and cheap FFT implementations for .NET that can be used in commercial products, we recently wrote our own implementations in C# and F#. We've actually made the C# implementation available as a product:
Note the performance results that show a competitor giving quadratic worst-case performance!
Interestingly, the F# implementation is slightly faster than the C#. The style is very similar so the implementations are roughly the same size. F# gives more potential for factoring so I'm probably going to refactor the FFT kernel into something written in a functional style with the aim of exploiting concurrency.