On Thu, Nov 14, 2013 at 4:45 PM, Charles Waldman <[email protected]> wrote:
> Can you post the raw data? It seems like there are just a couple of "bad" > sizes, I'd like to know more precisely what these are. > Indeed. Several of the sizes generated by logspace(2, 7, 25) are prime numbers, where numpy.fft is actually O(N^2) and not the usual O(NLogN). There is unfortunately no freely (aka BSD-like licensed) available fft implementation that works for prime (or 'close to prime') numbers, and implementing one that is precise enough is not trivial (look at Bernstein transform for more details). David > > It's typical for FFT to perform better at a sample size that is a power of > 2, and algorithms like FFTW take advantage of factoring the size, and > "sizes that are products of small factors are transformed most efficiently." > > - Charles > > On Thu, Nov 14, 2013 at 10:18 AM, Max Linke <[email protected]> wrote: > >> Hi >> >> I noticed some strange scaling behavior of the fft runtime. For most >> array-sizes the fft will be calculated in a couple of seconds, even for >> very large ones. But there are some array sizes in between where it will >> take about ~20 min (e.g. 400000). This is really odd for me because an >> array with 10 million entries is transformed in ~2s. Is this typical for >> numpy? >> >> I attached a plot and an ipynb to reproduce and illustrate it. >> >> best Max >> >> _______________________________________________ >> NumPy-Discussion mailing list >> [email protected] >> http://mail.scipy.org/mailman/listinfo/numpy-discussion >> >> > > _______________________________________________ > NumPy-Discussion mailing list > [email protected] > http://mail.scipy.org/mailman/listinfo/numpy-discussion > >
_______________________________________________ NumPy-Discussion mailing list [email protected] http://mail.scipy.org/mailman/listinfo/numpy-discussion
