Fast Fourier Transform

FFT

mpmath.fft(values)

Computes the Discrete Fourier Transform (DFT) of a sequence.

It uses the radix-2 Cooley-Tukey algorithm for power-of-two lengths and Bluestein’s algorithm for all other lengths.

Examples

>>> from mpmath import mp
>>> mp.pretty = True
>>> mp.fft([1, 0, 0, 0])
[1.0, (1.0 + 0.0j), 1.0, (1.0 + 0.0j)]
>>> mp.fft([1 + 2j, 1 + 2j])
[(2.0 + 4.0j), (0.0 + 0.0j)]
>>> mp.fft([1, 2, 3, 4])
[10.0, (-2.0 + 2.0j), -2.0, (-2.0 - 2.0j)]
>>> [mp.chop(x) for x in mp.fft([1, 2, 1])]
[4.0, (-0.5 - 0.866025403784439j), (-0.5 + 0.866025403784439j)]

Inverse FFT

mpmath.invfft(values)

Computes the inverse Discrete Fourier Transform (IDFT) of a sequence.

It uses the radix-2 Cooley-Tukey algorithm for power-of-two lengths and Bluestein’s algorithm for all other lengths.

Examples

>>> from mpmath import mp
>>> mp.pretty = True
>>> mp.invfft([1, 1, 1, 1])
[1.0, (0.0 + 0.0j), 0.0, (0.0 + 0.0j)]
>>> x = [1, 2, 3, 4]
>>> mp.invfft(mp.fft(x))
[(1.0 + 0.0j), (2.0 + 0.0j), (3.0 + 0.0j), (4.0 + 0.0j)]
>>> mp.invfft(mp.fft([1.0 + 1.0j, 2.0 + 2.0j, 3.0 + 3.0j]))
[(1.0 + 1.0j), (2.0 + 2.0j), (3.0 + 3.0j)]