在 FFT 中,我们经常会写出:
w*=wn;
这样的语句来计算单位根(的幂),但是这样搞在 n 较大时误差会很严重,直接影响就是不能压太多位,但是如果我们对于每个单位根(的幂)都用三角函数计算,像这样:
const double pi2=acos(-1);
const complex<double> w(cos(pi2*i/n),sin(pi2*i/n));
那么运行速度就会很慢,我们可以加一个语句,每隔数次循环就重新用三角函数计算:
if(!(i%512))w=cp(cos(pi2*i/n),sin(pi2*i/n));