Fast Fourier Transform (FFT)

void fft(Complex[] a, boolean invert) {
  int n = a.length;
  if (n == 1) return;
  Complex[] a0 = new Complex[n/2], a1 = new Complex[n/2];
  for (int i = 0; i < n/2; i++) { a0[i] = a[2*i]; a1[i] = a[2*i+1]; }
  fft(a0, invert); fft(a1, invert);
  double ang = 2 * Math.PI / n * (invert ? -1 : 1);
  Complex w = new Complex(1, 0), wn = new Complex(Math.cos(ang), Math.sin(ang));
  for (int i = 0; i < n/2; i++) {
    a[i] = a0[i].add(w.mul(a1[i]));
    a[i + n/2] = a0[i].sub(w.mul(a1[i]));
    if (invert) { a[i].divBy(2); a[i + n/2].divBy(2); }
    w = w.mul(wn);
  }
}