SciPy's FFT algorithms gain their speed by a recursive divide and conquer strategy. This relies on efficient functions for small prime factors of the input length. Thus, the transforms are fastest when using composites of the prime factors handled by the fft implementation. If there are efficient functions for all radices <= :None:None:`n`
, then the result will be a number :None:None:`x`
>= target
with only prime factors < :None:None:`n`
. (Also known as :None:None:`n`
-smooth numbers)
The result of this function may change in future as performance considerations change, for example, if new prime factors are added.
Calling fft
or ifft
with real input data performs an 'R2C'
transform internally.
Length to start searching from. Must be a positive integer.
True if the FFT involves real input or output (e.g., rfft
or hfft
but not fft
). Defaults to False.
The smallest fast length greater than or equal to target
.
Find the next fast size of input data to fft
, for zero-padding, etc.
On a particular machine, an FFT of prime length takes 11.4 ms:
>>> from scipy import fft
... rng = np.random.default_rng()
... min_len = 93059 # prime length is worst case for speed
... a = rng.standard_normal(min_len)
... b = fft.fft(a)
Zero-padding to the next regular length reduces computation time to 1.6 ms, a speedup of 7.3 times:
>>> fft.next_fast_len(min_len, real=True) 93312
>>> b = fft.fft(a, 93312)
Rounding up to the next power of 2 is not optimal, taking 3.0 ms to compute; 1.9 times longer than the size given by next_fast_len
:
>>> b = fft.fft(a, 131072)See :
The following pages refer to to this document either explicitly or contain code examples using this.
scipy.fft._basic.fft
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them