主题

主题

 
   

雷德算法

一个小算法的感觉。

拿一个0到2^n-1的自然数序列。

比方说

0 1 2 3 4 5 6 7

我们转换为二进制状态,那么这个序列就是

000 001 010 011 100 101 110 111

接下来我们模拟FFT的位置交换,即:

0 1 2 3 4 5 6 7

0 2 4 6 1 3 5 7

0 4 2 6 1 5 3 7

发现最终的序列变为了

000 100 010 110 001 101 011 111

雷德算法就是用于求出这个倒序的数列。

那么开始抄别人的玩意:

由上面的表可以看出,按自然顺序排列的二进制数,其下面一个数总是比其上面一个数大1,即下面一个数是上面一个数在最低位加1并向高位进位而得到的。

而倒位序二进制数的下面一个数是上面一个数在最高位加1并由高位向低位进位而得到。 

I、J都是从0开始,若已知某个倒位序J,要求下一个倒位序数:

应先判断J的最高位是否为0。

这可与k=N/2相比较,因为N/2总是等于100的。

如果k>J,则J的最高位为0,只要把该位变为1(J与k=N/2相加即可),就得到下一个倒位序数;

如果K<=J,则J的最高位为1,可将最高位变为0(J与k=N/2相减即可)。然后还需判断次高位,这可与k=N\4相比较,若次高位为0,则需将它变为1(加N\4即可)其他位不变,既得到下一个倒位序数;若次高位是1,则需将它也变为0。然后再判断下一位……

代码如下:

    void Rader(int len) {

        int vi,vj,vt=0;

        for(vi=0; vi<len; vi++) {

            if(vi>vt)std::swap(Po[vi],Po[vt]);//否则就交换两次白忙活了

            for(vj=(len>>1); (vt^=vj)<vj; vj>>=1);

        }

    }

Po就是直接储存的数字了。

这里直接搬了FFT的代码……

 
 
评论
 
 
热度(1)