Fourier : FFT



La DFT est un calcul long car il nécessite NxN calculs en revanche et compte tenu de certaines proprités de la DFT on peut se simplifier le calcul par recurssivité des termes pair/impair pour obtenir un calcul qui au final ne coutera que NxlogN opérations …

Ci après le code de la Fast Fourier Transform alias FFT

//-------------
// Fast Fourier Transform ...
// v Reel
function fft(X) {
  const x = [...X];
  const N = x.length;
  if (N <= 1) {
    return x;
  }

  // var X = x.slice();
  const hN = N / 2;
  let even = [];
  let odd = [];
  even.length = hN;
  odd.length = hN;
  // on separe even/odd
  for (let i = 0; i < hN; ++i) {
    even[i] = x[i * 2];
    odd[i] = x[i * 2 + 1];
  }
  // on lance la recursivite
  even = fft(even);
  odd = fft(odd);
  // au retour on calcul ...
  const w = -2 * Math.PI;
  for (var k = 0; k < hN; ++k) {
    if (!(even[k] instanceof Complex))
      even[k] = new Complex(even[k], 0);
    if (!(odd[k] instanceof Complex))
      odd[k] = new Complex(odd[k], 0);
    let p = k/N;
    let Wk = new Complex(0,w*p);
    Wk.expW(Wk).mul(odd[k],Wk);
    x[k] = even[k].add(Wk, odd[k]);
    x[k + hN] = even[k].sub(Wk, even[k]);
  }
  return x;
}