OI

F?T

Posted by wyj on October 9, 2018

今天学习了分支预测。非常震惊,CPU居然在判断语句执行之前就有97%的可能性预测对语句的结果。于是回顾了一下我的F?T代码。

首先,我的FFT是这样的(从七年级开始时就差不多这样):

void FFT(cmp *a){
    for(int i=0;i<N;i++)
        if(i<rev[i])swap(a[i],a[rev[i]]);
    for(int i=0;i<lg;i++)
        for(int j=0;j<N;j++)if(!(j&1<<i)){
            int x=j^1<<i;
            a[x]*=w[(j&(1<<i)-1) << lg-1-i];
            //现在我自己都忘了这句话是什么意思
            cmp tmp=a[j]+a[x];
            a[x]=a[j]-a[x];a[j]=tmp;
        }
}

具体效率如何呢?比别人同样的FFT,某些题三遍变两遍后还是慢一倍。

这是我当时看着这篇神文中的图片自己意会的,所以和别人算导上看来的写法差别很大(还有多项式求逆等等,差别都很大)。比别人短一些并且少一重循环,怎么就这么慢呢?现在推测,可能是那个if经常分支预测失败(并且这个代价很大),因为它的确没有什么规律。相反,看别人的代码,循环紧凑,没有分支,内存顺序,便于编译器展开,当然快了。
//2018.11.18 UPD: 现在猜想慢的主要原因应该是对于w数组的寻址

前不久学习了FWT,看了那三种变换的中心思想,我就又意会了,意会出来居然是两重循环,而且和FFT几乎一样。真奇怪,我自己的FWT和自己的FFT像,别人的FFT和别人的FWT像。我觉得这两重for就是很显然的呀,看到\(FWT(a)=\{FWT(a_0)+FWT(a_1),FWT(a_0)-FWT(a_1)\}\)的时候脑子里应该马上冒出来蝴蝶变换,然后枚举层数一层一层做啊。下面是我的FWT(XOR)代码,和FFT真的像:

void FWT(int64 *a,int f){
    for(int i=0;i<lg;i++)
        for(int j=0;j<N;j++)if(j&1<<i){
            int t=j^1<<i;int64 tmp=a[t]+a[j];
            a[j]=(a[t]-a[j])*f%mod;
            a[t]=tmp*f%mod;
        }
}

今天去看了FWT那题的题解,发现我这种写法居然叫做FMT,FMT的and和or都和我一模一样。不是一样的吗,为什么就和Möbius 扯上关系了。而且还都说这么写不能xor。。。我真的搞不懂了,xor和别的两个有什么本质区别吗???
(2018.11.07 UPD : FMT之所以叫做FMT是因为它是从莫比乌斯反演推出来的,所以不能应用于xor )

更为诡异的是,我FFT和FWT,写法都一样,但是FFT比别人的慢6倍,FWT却和别人不相上下。可能是因为全是位运算,分支预测失败的代价更小一些吧。

总结:常数真的玄学。