transformRadix2 function

void transformRadix2(List<double> real, List<double> imag)

Implementation

void transformRadix2(List<double> real, List<double> imag) {
  var n = real.length;
  if (n != imag.length) throw new RangeError("实部虚部长度不匹配");
  if (n == 1) return;
  var levels = -1;
  for (var i = 0; i < 32; i++) {
    if (1 << i == n) {
      levels = i;
      break;
    }
  }
  if (levels == -1) throw new RangeError("长度非2的n次方");

  var cosTable = List<double>.filled((n / 2).floor(), 0);
  var sinTable = List<double>.filled((n / 2).floor(), 0);

  for (var i = 0; i < (n / 2).floor(); i++) {
    cosTable[i] = math.cos((2 * math.pi * i) / n);
    sinTable[i] = math.sin((2 * math.pi * i) / n);
  }

  for (var i = 0; i < n; i++) {
    var j = reverseBits(i, levels);
    if (j > i) {
      var temp = real[i];
      real[i] = real[j];
      real[j] = temp;
      temp = imag[i];
      imag[i] = imag[j];
      imag[j] = temp;
    }
  }

  for (var size = 2; size <= n; size *= 2) {
    var halfsize = (size / 2).floor();
    var tablestep = (n / size).floor();
    for (var i = 0; i < n; i += size) {
      for (var j = i, k = 0; j < i + halfsize; j++, k += tablestep) {
        var l = j + halfsize;
        var tpre = real[l] * cosTable[k] + imag[l] * sinTable[k];
        var tpim = -real[l] * sinTable[k] + imag[l] * cosTable[k];
        real[l] = real[j] - tpre;
        imag[l] = imag[j] - tpim;
        real[j] += tpre;
        imag[j] += tpim;
      }
    }
  }
}