🚀 go-pugleaf

jpp@pipo.paris.sgi.com (Jean-Pierre Panziera - SGI PARIS) writes:

>In article <1993Jan4.154245.13258@crl.dec.com>, payne@crl.dec.com
>(Andrew Payne) writes:
*** Stuff deleted ***
>  An array of 1024 complex numbers indeed uses 8 Kbytes. However to compute an 
>  FFT you need an extra array of Sines and Cosines of same size (8 kBytes).
>  The total space required for this FFT is then at least 8+8 = 16 kBytes.
>  So the assumption "just fits in the on-chip 8K D cache" seems abusive. ???
Not quite true.  If I recall correctly, you need a table of 256 sine or
cosine values.  The rest are computed through index arithmetic and sign
conversion.  But the basic point is true.  It all doesn't fit in a 8K
cache.  I assume that there is some effort to optimize memory accesses
so that main memory access time is not a problem.  As an aside, a DSP
computer salesman once told me that the time to compute a 1024 point
complex FFT is an important selling point and his company ( and others)
expended great amounts of time to make this number as small as possible.
Even to the detriment of other parts of the software library.