In CP4 Page 517, code for an in-place FFT is written. However, it contains (multiple) errors. Here is a working version of the same function.
typedef complex<long double> cd;
const double PI = acos(-1.0);
int reverseBit(int x, int m) { // m is the binary length A.size()-1
int ret = 0;
for (int k = 0; k < m; k++) {
if (x & (1 << k)) ret |= (1 << (m - 1 - k));
}
return ret;
}
void FFT(vector<cd> &A) { // evaulates A at the nth roots of unity for n = 2^k >= A.size()
int m = 0;
while ((1 << m) < (int)A.size()) m++;
A.resize(1 << m, 0); // size of A should be a power of 2, resizes A
for (int k = 0; k < (int)A.size(); k++) { // sort to bit-reversal permutation
if (k < reverseBit(k, m)) swap(A[k], A[reverseBit(k, m)]);
}
for (int n = 2; n <= (int)A.size(); n <<= 1) {
for (int k = 0; 2 * k < n; k++) {
// we are going to get the kth and k+n/2th element of each length n block
cd x = cd(cos(2 * PI * k / n), sin(2 * PI * k / n)); // nth root of unity
for (int j = 0; j < (int)A.size(); j += n) { // apply to every sub-array of length n
cd A0k = A[k + j]; // previously computed
cd A1k = A[k + j + n / 2]; // previously computed
A[k + j] = A0k + x * A1k;
A[k + j + n / 2] = A0k - x * A1k;
}
}
}
}
In CP4 Page 517, code for an in-place FFT is written. However, it contains (multiple) errors. Here is a working version of the same function.