[phobos] FFT

[Andrei Alexandrescu]

David Simcha wrote:
> Yea, I actually thought of stuff this and did a version with a simple 
> linear interpolation to get numbers between a relatively small table of 
> precomputed values.  It was neither as fast nor as simple as the current 
> solution, though it was more space efficient.  sin() and cos() are 
> pretty fast (<100 clock cycles, apparently) so a few mathematical 
> operations to round indices to the nearest integer, perform 2 table 
> lookups and linearly interpolate can easily destroy most of the speed 
> advantage.

Then I think a reasonable step to do is what researchers always do - 
take a look at what others have done.

> The key thing about the current solution is that, at every sub-FFT size, 
> the elements are accessed in sequential order without a stride or 
> anything

Mmm, that sounds like forward range to me :o). (I'm sure there are other 
reasons for which you need random access, so no need to reply unless you 
got illuminated like those people in the "Windows 7 was my idea" 
commercials. Man what crappy commercials.)


Andrei