[phobos] FFT

[Andrei Alexandrescu]

On 08/03/2010 11:01 PM, David Simcha wrote:
> Ok, I've got some more optimizations.  I figured out that it's worth
> trading off some space to make the sin/cos lookup tables be in
> contiguous memory blocks for all sub-FFTs. I'm now down to ~340 ms on my
> benchmark, but fresh out of optimization ideas.

I meant to say this after your previous post: function tabulation is not 
all. What people do is they approximate functions with a few of their 
Taylor expansion terms, often in conjunction with tables.

For my thesis I needed a fast tanh. I dug up a paper that had some weird 
formulas depending on the magnitude of the argument. I first built a 
table and then I interpolated using the formulas in between the table 
elements. It was a smashing success.

Google for <<fast sine approximation>> or so, there seems to be plenty 
of good stuff out there.


Andrei