[SciPy-dev] fft code for testing

[Chuck Harris]

Hi

> -----Original Message-----
> From: Pearu Peterson [mailto:pearu at scipy.org]
> Sent: Saturday, May 31, 2003 2:26 PM
> To: scipy-dev at scipy.net
> Subject: RE: [SciPy-dev] fft code for testing
> 
> 
> 
> 
> On Sat, 31 May 2003, Chuck Harris wrote:
> 
> > > So, when n is not a power-of-two, then at least 31 C int 
> comparisons are
> > > required. I wonder if this is the lowest bound of #operations or
> > > can we do better?
> > 
> > Probably, but by the time we are doing 1024 point 
> transforms the time
> > spent in checking doesn't matter, whereas for the small 
> numbers you can
> > hardly beat the direct comparisons.
> 
> ... which gives me an idea to factor the comparison sequence by
> introducing some auxiliary tests:
> 
> int foo(int n) 
> {
>   int ok = 1;
>   if (n<0x100)
>     if (n==0x1 || n==0x2 || n==0x4 || n==0x8 ||
> 	n==0x10 || n==0x20 || n==0x40 || n==0x80);
>     else ok = 0;
>   else if (n<0x10000)
>     if (n==0x100 || n==0x200 || n==0x400 || n==0x800 ||
> 	n==0x1000 || n==0x2000 || n==0x4000 || n==0x8000);
>     else ok = 0;
>   else if (n==0x10000 || n==0x20000 || n==0x40000 || n==0x80000 ||
> 	   n==0x100000 || n==0x200000 || n==0x400000 || n==0x800000 ||
> 	   n==0x1000000 || n==0x2000000 || n==0x4000000 || 
> n==0x8000000 ||
> 	   n==0x10000000 || n==0x20000000 || n==0x40000000);
>   else
>     ok = 0;
>   return ok;
> }
> 
> and as a result, much less operations are required for random small
> integers.
> 
> It would be a nice homework to find optimal steps for 
> auxiliary less-tests
> by taking also into account the distribution of fft sizes used in real
> applications... ;-)
> 
> Pearu

Yep, that would work. Binary search would be the result of taking this all the
way, and it appears that the case statement is actually treated that way by
gcc.

I find that when doing interactive stuff I use fft sizes 256 ... 1024, because I'm
usually looking to plot the results. For actual production type stuff the sizes are
in the range 4Kib ... 64Kib (fourier spectroscopy, mostly). Wonder If we should decide
on a range of sizes in which the fft should be optimum?

Chuck