[Numpy-discussion] Fast sizes for FFT

RayS rays at blue-cove.com
Wed Dec 24 12:21:47 EST 2014


At 06:47 PM 12/23/2014, you wrote:
>The performance of fftpack depends very strongly on the array size 
>-- sizes that are powers of two are good, but also powers of three, 
>five and seven, or numbers whose only prime factors are from 
>(2,3,5,7). For problems that can use padding, rounding up the size 
>(using np.fft.fft(x, n=size_with_padding)) to one of these multiples 
>makes a big difference.

Checking some of my old code, we had typically done:
     N2 = 2**int(math.ceil(math.log(N,2)))
and then something like
     abs(rfft(data[minX:maxX, ch]*weightingArray, 
N2))[1:numpy.floor(N2/2)+1] * norm_factor

In the PDF linked, I can see where N % 3,5,7 could really help; we 
just don't do giant FFTs (>2**22) often. However, users would often 
see loooong waits if/when they selected prime N on a data plot and 
asked for the full FFT without padding enabled - like ~5 seconds on a Core 2.

When released we'll certainly use the new functionality.

- Ray 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20141224/64722049/attachment.html>


More information about the NumPy-Discussion mailing list