Fonction numpy + constante à utiliser

from numpy import tile, interp, linspace, exp, r_, pi

DFT (lent)

def dft(x):return exp(-2j * pi * r_[:len(x)] / len(x))**r_[[r_[:len(x)]]].T @ x

FFT (limité aux éléments de puissance de 2)

def fft(x):return tile(fft(x[::2]), 2) + (r_[[[1],[-1]]] * (exp(-2j * pi * r_[:len(x) // 2] / len(x)) * fft(x[1::2]))).ravel() if len(x) > 1 else x

FFT (pas de limite sur le nombre d'éléments, long)

def fft(x):return interp(linspace(0, 1 << (len(f'{len(x) - 1:b}')), len(x)), r_[:1 << (len(f'{len(x) - 1:b}'))], fft(r_[x, [0] * ((1 << (len(f'{len(x) - 1:b}'))) - len(x))])) if ('1' in f'{len(x):b}' [1:]) else tile(fft(x[::2]), 2) + (r_[[[1], [-1]]] * (exp(-2j * pi * r_[:len(x) // 2] / len(x)) * fft(x[1::2]))).ravel() if len(x) > 1 else x

Contrôle de fonctionnement

from numpy import sin, fft, random
import matplotlib.pyplot as plt

Forme d'onde à convertir

Synthèse de 5 ondes $ sin $ avec fréquence et amplitude aléatoires, $ 2048 (= 2 ^ {11}) $ élément

n = 1 << 11
x = linspace(0, 2 * pi, n)
y = 0

for w in n / 2 * random.rand(5):
    y += random.rand() * sin(w * x)

plt.plot(x, y, lw = .3)

Numpy.fft.fft

%timeit fft.fft(y)
plt.plot(abs(fft.fft(y))**2)

9.01 µs ± 42.9 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

DFT

%timeit dft(y)
plt.plot(abs(dft(y))**2)

568 ms ± 899 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

FFT (limité à l'élément de puissance de 2)

%timeit fft(y)
plt.plot(abs(fft(y))**2)

51.2 ms ± 76.9 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

FFT (plus long)

%timeit fft(y)
plt.plot(abs(fft(y))**2)

54.1 ms ± 159 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Résumé

La FFT de Numpy est trop tôt! La sortie est la même, mais vous pouvez voir que la FFT est environ 10 fois plus rapide que la simple DFT.

[Python] One-liner FFT (transformation de Fourier rapide) et autres folies