[Python] One-liner FFT (Fast Fourier Transform) and other madness

Numpy function + constant to use

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

DFT (slow)

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

FFT (limited to power elements of 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 (no limit on the number of elements, 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

Operation check

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

Waveform to convert

Synthesis of 5 $ sin $ waves with random frequency and amplitude, $ 2048 (= 2 ^ {11}) $ element

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)

image.png

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) image.png

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) image.png

FFT (limited to power elements of 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) image.png

FFT (longer one)

%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) image.png

Summary

Numpy's FFT is too early! The output is the same, but you can see that the FFT is about 10 times faster than just the DFT.

Recommended Posts

[Python] One-liner FFT (Fast Fourier Transform) and other madness
FFT (Fast Fourier Transform): Formulas and Implementation Examples for Implementation
Signal processing in Python (1): Fourier transform
[Scientific / technical calculation by Python] 1D-3D discrete fast Fourier transform, scipy
Drawing with Bezier curve and Fourier transform
Fourier transform the wav file read by Python, reverse transform it, and write it again.
Image processing from scratch with python (5) Fourier transform
How to confirm the Persival theorem using the Fourier transform (FFT) of matplotlib and scipy