<p dir="auto"><em>Original ticket <a href="http://projects.scipy.org/numpy/ticket/1266" rel="nofollow">http://projects.scipy.org/numpy/ticket/1266</a> on 2009-10-19 by trac user koehler, assigned to unknown.</em></p>
<p dir="auto">Although the documenttation of numpy.fft.fft states that:<br>
"This is most efficient for n a power of two. This also stores a cache of working memory for different sizes of fft's, so you could theoretically run into memory problems if you call this too many times with too many different n's." ,I think that it may be important to report this oddity in the fft runtime.<br>
Dependent on the array length, the fft runtime varies really extreme:</p>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="[ipython shell, from numpy import *]
In [1]: %time fft.fft(zeros(119516))
CPU times: user 22.83 s, sys: 0.39 s, total: 23.23 s
Wall time: 23.53 s

In [3]: %time fft.fft(zeros(119517))
CPU times: user 36.33 s, sys: 0.08 s, total: 36.40 s
Wall time: 36.51 s

In [5]: %time fft.fft(zeros(119518))
CPU times: user 4.88 s, sys: 0.08 s, total: 4.96 s
Wall time: 5.02 s

In [7]: %time fft.fft(zeros(119519))
CPU times: user 0.45 s, sys: 0.00 s, total: 0.45 s
Wall time: 0.45 s

In [9]: %time fft.fft(zeros(119515))
CPU times: user 0.07 s, sys: 0.00 s, total: 0.08 s
Wall time: 0.08 s

In [11]: %time fft.fft(zeros(119514))
CPU times: user 15.84 s, sys: 0.06 s, total: 15.90 s
Wall time: 15.95 s

In [13]: %time fft.fft(zeros(119513))
CPU times: user 272.75 s, sys: 1.03 s, total: 273.78 s
Wall time: 275.63 s"><pre class="notranslate"><code class="notranslate">[ipython shell, from numpy import *]
In [1]: %time fft.fft(zeros(119516))
CPU times: user 22.83 s, sys: 0.39 s, total: 23.23 s
Wall time: 23.53 s

In [3]: %time fft.fft(zeros(119517))
CPU times: user 36.33 s, sys: 0.08 s, total: 36.40 s
Wall time: 36.51 s

In [5]: %time fft.fft(zeros(119518))
CPU times: user 4.88 s, sys: 0.08 s, total: 4.96 s
Wall time: 5.02 s

In [7]: %time fft.fft(zeros(119519))
CPU times: user 0.45 s, sys: 0.00 s, total: 0.45 s
Wall time: 0.45 s

In [9]: %time fft.fft(zeros(119515))
CPU times: user 0.07 s, sys: 0.00 s, total: 0.08 s
Wall time: 0.08 s

In [11]: %time fft.fft(zeros(119514))
CPU times: user 15.84 s, sys: 0.06 s, total: 15.90 s
Wall time: 15.95 s

In [13]: %time fft.fft(zeros(119513))
CPU times: user 272.75 s, sys: 1.03 s, total: 273.78 s
Wall time: 275.63 s
</code></pre></div>
<p dir="auto"><em>Original ticket <a href="http://projects.scipy.org/numpy/ticket/579" rel="nofollow">http://projects.scipy.org/numpy/ticket/579</a> on 2007-09-14 by <a class="user-mention notranslate" data-hovercard-type="user" data-hovercard-url="/users/cournape/hovercard" data-octo-click="hovercard-link-click" data-octo-dimensions="link_type:self" href="https://github.com/cournape">@cournape</a>, assigned to unknown.</em></p>
<p dir="auto">See <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="7725267" data-permission-text="Title is private" data-url="https://github.com/numpy/numpy/issues/1104" data-hovercard-type="issue" data-hovercard-url="/numpy/numpy/issues/1104/hovercard" href="https://github.com/numpy/numpy/issues/1104">#1104</a> and <a href="http://en.wikipedia.org/wiki/Bluestein's_FFT_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Bluestein's_FFT_algorithm</a></p>