Fast Fourier Transform

FFT

mpmath.fft(values)

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

Raises NotImplementedError if the input sequence length is not a power of 2.

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)]

Inverse FFT

mpmath.invfft(values)

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

Raises NotImplementedError if the input sequence length is not a power of 2.

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)]