Я недавно выучил алгоритм БПФ.
Я применил это к проблеме быстрого умножения очень большого натурального числа после этого псевдокода,
Let A be array of length m, w be primitive m-th root of unity.
Goal: produce DFT F(A): evaluation of A at 1, w, w^2,...,w^{m-1}.
FFT(A, m, w)
{
if (m==1) return vector (a_0)
else {
A_even = (a_0, a_2, ..., a_{m-2})
A_odd = (a_1, a_3, ..., a_{m-1})
F_even = FFT(A_even, m/2, w^2) //w^2 is a primitive m/2-th root of unity
F_odd = FFT(A_odd, m/2, w^2)
F = new vector of length m
x = 1
for (j=0; j < m/2; ++j) {
F[j] = F_even[j] + x*F_odd[j]
F[j+m/2] = F_even[j] - x*F_odd[j]
x = x * w
}
return F
}
Он отлично работает, но я нашел лучший код, который выполняет ту же работу без рекурсии, а также работает намного быстрее.
Я попытался выяснить, как это работает построчно, но мне это не удалось.
Я был бы очень признателен, если бы вы подробно объяснили мне, что происходит в первых двух циклах for (не в математической части)
Ниже новый код
typedef complex<double> base;
void fft(vector<base> &a, bool invert)
{
int n = a.size();
for (int i = 1, j = 0; i < n; i++){
int bit = n >> 1;
for (; j >= bit; bit >>= 1) j -= bit;
j += bit;
if (i < j) swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1){
double ang = 2 * M_PI / len * (invert ? -1 : 1);
base wlen(cos(ang), sin(ang));
for (int i = 0; i < n; i += len){
base w(1);
for (int j = 0; j < len / 2; j++){
base u = a[i + j], v = a[i + j + len / 2] * w;
a[i + j] = u + v;
a[i + j + len / 2] = u - v;
w *= wlen;
}
}
}
if (invert)
{
for (int i = 0; i < n; i++)
a[i] /= n;
}
}