上次仅仅读了徐明宽的论文的一部分,就觉得很强.
于是我又从同学的介绍和毛啸的论文中get到了一点FFT的新技能
虽然还有一个更高阶的技能不会用.
FFT的优化论文中提了很多
减少DFT次数(最后再IDFT,预处理DFT)
利用循环卷积(不会,待研究)
分治FFT小范围暴力(效果显著)
快速幂次数的优化(addition chain,大佬说没什么用,我也没有仔细看)
然后就到了重点:
一个新的技巧!!!
十分强大!!!
然而我只看懂了前半部分.
所以只提前半部分.
论文里讲得十分详细,也给出了证明.
简洁一点说
就是把FFT(a) FFT(b)
这两次FFT
变成一次FFT
只需要构造fp=a+bi
对fp做FFT
然后计算出他的共轭复数fq的点值表示.
fq[0]=fp[0]
fq[i]=fp[u-i] (i>=1) u 为 长度
然后计算c=a卷b的点值表示
c[i]=(fp[i]+fq[i])*单位虚数*(fq[i]-fp[i])/4
就好了
证明详见论文(主要是因为我不会推)
代码实现不难.
只要将
FFT(a); FFT(b); for (int i=0; i<u; ++i) a[i]*=b[i];
改为
for (int i=0; i<u; ++i) fp[i]=virt(a[i].real(),b[i].real()); FFT(fp); fq[0]=conj(fp[0]); for (int i=1; i<u; ++i) fq[i]=conj(fp[u-i]); for (int i=0; i<u; ++i) a[i]=(fp[i]+fq[i])*(xi*(fq[i]-fp[i])),a[i]/=4;
即可.
可以压去1/3常数
带来的不良之处就是精度会大幅降低,不过对于整系数FFT精度绰绰有余
论文后面还有更优的的方法,只是我并不理解.
仅仅理解了不到十分之一的内容,就受益匪浅啊!
奇怪的是,这篇论文@到了method of four russians,不禁有些奇怪.看来我的理解还不够.
method of four russians 不是一种算法,而是一种思想啊!