Newsgroups: sci.math.num-analysis,sci.math,comp.lang.c,comp.lang.c++,comp.dsp
Path: usc!howland.reston.ans.net!bogus.sura.net!darwin.sura.net!sgiblab!sono!porky!mayer
From: mayer@sono.uucp (Ron Mayer)
Subject: Re: another SUMMARY: FFT in C (Best?,Fastest?,probably not) (part 2 of 2)
In-Reply-To: mayer@acuson.com's message of Fri, 19 Mar 1993 03: 43:48 GMT
Message-ID: <MAYER.93Mar18211416@porky.sono.uucp>
Sender: mayer@acuson.com (Ron Mayer)
Organization: Acuson; Mountain View, California
References: <pm860605.125.732416789@longs.LANCE.ColoState.Edu>
	<1993Mar19.034348.16124@acuson.com>
Date: Fri, 19 Mar 1993 05:14:16 GMT
Lines: 23
Xref: usc sci.math.num-analysis:7477 sci.math:41881 comp.lang.c:67196 comp.lang.c++:39621 comp.dsp:5668


One thing I forgot to mention; in the timing loops you probably want
to significantly reduce the number of iterations for architectures weaker
than a sun sparc. To do this, edit one of 256's in the line
   > lop = 2+256*256/num;
in both time_*.c files.  The timing loops will calculate things
correctly as long as "lop", the number of iterations, is even.
Failure to do this will make the compare_ffts script take tens of
minutes on a sun3.

It is also interesting to note that while everyone "knows" that a fft
takes O(n*log(n)) time; different algorithms differ widely in the O(n)
and O(log(n)) components which are quite significant for short (often
about 20% for <100 point) FFTs.  Most published routines
carefully optimize their inner loop; but tend to ignore the O(n)
loops; making their routines unnecessarily slow for short transforms.

My routines were once intended for applying filters to real-time 32
element blocks of data; so I went through great (probably excessive)
lengths to minimize the O(n) and O(log(n)) components.

    Ron Mayer
    mayer@acuson.com

