Chlience

【算法】FFT/DFT 中的二进制翻转问题
在 $FFT/NTT$ 中,我们经常看到一个这样的式子:for(int i = 0; i < n; ++ i...
扫描右侧二维码阅读全文
16
2019/01

【算法】FFT/DFT 中的二进制翻转问题

在 $FFT/NTT$ 中,我们经常看到一个这样的式子:

for(int i = 0; i < n; ++ i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

然后在每次 $DFT/IDFT$ 中则会出现:

for(int i = 0; i < n ; ++ i)
    if(i < rev[i])
        swap(a[i] , a[rev[i]]);

为什么呢?

对 $FFT/NTT$ 比较了解的可能会脱口而出:因为蝴蝶变换导致的二进制翻转(吾等瑟瑟发抖
然而过了这么久还是一知半解,直接背的代码

还是具体来讲一下吧

在 $FFT/NTT$ 中,为了实现加速卷积的过程,我们将整个数组按照二进制位划分为了很多个小区间,然后蝴蝶变换一路向上合并,直至回到原来的排列

那么最后划分的小区间是个什么样子呢?
对于一个长度为 $8$ 的序列,有:

FFT

第一次按照最末位划分,紧接着按照倒数第二位...
也就是说,相当于按照 二进制位从后往前 的顺序进行排序

那么,考虑对于每个位置 $i$ 二进制翻转之后的位置即 $rev[i]$
显然如果 $rev[a]=b,rev[b]=a$
所以有:

for(int i = 0; i < n ; ++ i)
    if(i < rev[i])
        swap(a[i] , a[rev[i]]);

如何求 $rev$?
显然如果朴素的求 $rev$ 时间复杂度为 $n\log n$
其实也不是不能接受嘛

不过为了实现更高效,考虑从之前已经得到的 $rev$ 处转移

对于当前位置 $i$,假设其二进制写作:$1010010$
$rev[i]$ 写作:$0100101$

显然,翻转后的二进制数相当于将第一位到倒数第二位翻转,然后将最后一位放到开头
显然第一位到倒数第二位位用二进制表示为 $101001$,即去掉最后一位,补上前导零后为 $0101001$,即 $i>>1$

翻转结果显然是 $rev[i>>1]$,去掉之前补上的前导零的影响即右移一位 $rev[i>>1]>>1$
最后将原数最后一位的影响补上 $(i \& 1) << (l - 1)$,$+$ 或者 $|$ 都可以,只不过 $|$ 更快罢了

所以写为代码的形式即:

for(int i = 0; i < n; ++ i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

感觉写完后对 $FFT$ 的理解更深了呢(雾

Last modification:January 16th, 2019 at 11:33 am

Leave a Comment