On Thu, Nov 14, 2013 at 4:45 PM, Charles Waldman <char...@crunch.io> 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 <max_li...@gmx.de> 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 >> NumPy-Discussion@scipy.org >> http://mail.scipy.org/mailman/listinfo/numpy-discussion >> >> > > _______________________________________________ > NumPy-Discussion mailing list > NumPy-Discussion@scipy.org > http://mail.scipy.org/mailman/listinfo/numpy-discussion > >
_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
