[SciPy-dev] fft code for testing

[Pearu Peterson]

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