splitFft static method

List<List<Complex>> splitFft(List<Complex> fFft)

Split a polynomial f in two polynomials.

Args: fFft: a polynomial in FFT representation

Format: FFT

Corresponds to algorithm 1 (splitfft_2) of Falcon's documentation.

Implementation

static List<List<Complex>> splitFft(List<Complex> fFft) {
  final int n = fFft.length;
  final List<Complex> w = phiRoots[n]!;
  final List<Complex> f0Fft = List.filled(n ~/ 2, Complex.zero);
  final List<Complex> f1Fft = List.filled(n ~/ 2, Complex.zero);

  for (int i = 0; i < n ~/ 2; i++) {
    f0Fft[i] = (fFft[2 * i] + fFft[2 * i + 1]) * 0.5;
    f1Fft[i] = (fFft[2 * i] - fFft[2 * i + 1]) * 0.5 * w[2 * i].conjugate();
  }

  return [f0Fft, f1Fft];
}