On Thu, 2013-11-14 at 17:19 +0000, David Cournapeau wrote: > 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). Ok I thought the fft is always O(N log N). But it makes sense that this only works if the input-size factorizes well. Thanks for clearing this up.
best Max > > 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 _______________________________________________ NumPy-Discussion mailing list [email protected] http://mail.scipy.org/mailman/listinfo/numpy-discussion
