今天学习了分支预测。非常震惊，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却和别人不相上下。可能是因为全是位运算，分支预测失败的代价更小一些吧。
