transform static method

void transform(Float64List real, Float64List imaginary)

Implementation

static void transform(Float64List real, Float64List imaginary) {
  final n = real.length;

  if (imaginary.length != n) {
    throw ArgumentError('FFT buffers must have the same length.');
  }

  if (n == 0) {
    return;
  }

  if ((n & (n - 1)) != 0) {
    throw ArgumentError('FFT input size must be a power of 2.');
  }

  int j = 0;
  for (int i = 1; i < n; i++) {
    int bit = n >> 1;
    while ((j & bit) != 0) {
      j ^= bit;
      bit >>= 1;
    }
    j ^= bit;

    if (i < j) {
      final realValue = real[i];
      real[i] = real[j];
      real[j] = realValue;

      final imaginaryValue = imaginary[i];
      imaginary[i] = imaginary[j];
      imaginary[j] = imaginaryValue;
    }
  }

  for (int length = 2; length <= n; length <<= 1) {
    final angle = -2 * math.pi / length;
    final stepReal = math.cos(angle);
    final stepImaginary = math.sin(angle);
    final halfLength = length >> 1;

    for (int start = 0; start < n; start += length) {
      double twiddleReal = 1;
      double twiddleImaginary = 0;

      for (int offset = 0; offset < halfLength; offset++) {
        final evenIndex = start + offset;
        final oddIndex = evenIndex + halfLength;

        final oddReal =
            real[oddIndex] * twiddleReal -
            imaginary[oddIndex] * twiddleImaginary;
        final oddImaginary =
            real[oddIndex] * twiddleImaginary +
            imaginary[oddIndex] * twiddleReal;

        real[oddIndex] = real[evenIndex] - oddReal;
        imaginary[oddIndex] = imaginary[evenIndex] - oddImaginary;
        real[evenIndex] += oddReal;
        imaginary[evenIndex] += oddImaginary;

        final nextTwiddleReal =
            twiddleReal * stepReal - twiddleImaginary * stepImaginary;
        twiddleImaginary =
            twiddleReal * stepImaginary + twiddleImaginary * stepReal;
        twiddleReal = nextTwiddleReal;
      }
    }
  }
}