On Fri, Nov 15, 2013 at 10:47 PM, Max Linke <[email protected]> wrote:
> 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. > To be exact, there *are* FFT-like algorithms for prime number size, but that's not implemented in numpy or scipy (see here: http://numpy-discussion.10968.n7.nabble.com/Prime-size-FFT-bluestein-transform-vs-general-chirp-z-transform-td3171.htmlfor an old discussion on that topic). cheers, David > > 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 >
_______________________________________________ NumPy-Discussion mailing list [email protected] http://mail.scipy.org/mailman/listinfo/numpy-discussion
