我发现了一篇关于适用于就地 FFT 的位反转算法的非常有趣的论文:“位反转排列的简单算法”,作者: Urszula Rutkowska,1990 年 (doi.org/10.1016/0165-1684(91)90008-7)。
但是,她的算法 G1 似乎无法正常工作,因为第一次迭代会导致 N1 = L << 1
出现越界错误和 swap(a + 1, a + N1);
.我假设 L
表示输入向量的长度。
拜托,有谁知道这篇论文是否有任何勘误表或如何修正算法?
论文的伪代码:
G1(L)
{int i,j,L1
N1,N2,a,b;
unsigned k;
j=0; L1=L-1;
N1=L<<1;N2=N1+1;
for(i=0;i<L1;i++)
{if(i<j)
{ a=i<<1;
b=j<<1;
swap(a,b);
swap(a+N2,b+N2);
swap(a+1,b+N1);
swap(b+1,a+N1);
}
else
if(i==j)
{ a=i<<1;
swap(a+1,a+N1);
}
k=L>>1;
while(k<=j){ j=j-k;
k=k>>1;
}
j+=k;
}
i<<=1;
swap(i+1,i+N1);
}
论文截图:
最佳答案
坦率地说,这是相当困惑的。我必须阅读论文以了解这个想法(为 L/4 运行 Gold 的算法 (G),然后推导出 L 的交换),然后将代码整理成正确的形式。这是我的最终结果。
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
static bool is_power_of_two(int L) { return L > 0 && (L & (L - 1)) == 0; }
static void swap(int i, int j) { printf("swap %d,%d\n", i, j); }
static void G(int L) {
assert(is_power_of_two(L));
int j = 0;
for (int i = 0; i < L - 1; i++) {
if (i < j) {
swap(i, j);
}
int k = L >> 1;
while (j >= k) {
j -= k;
k >>= 1;
}
j += k;
}
}
static void G1(int L) {
assert(is_power_of_two(L));
if (L < 4) {
return;
}
int j = 0;
int N1 = L >> 1;
int N2 = N1 + 1;
int L2 = L >> 2;
for (int i = 0; i < L2 - 1; i++) {
if (i < j) {
int a = i << 1;
int b = j << 1;
swap(a, b);
swap(a + N2, b + N2);
swap(a + 1, b + N1);
swap(b + 1, a + N1);
} else if (i == j) {
int a = i << 1;
swap(a + 1, a + N1);
}
int k = L2 >> 1;
while (j >= k) {
j -= k;
k >>= 1;
}
j += k;
}
int a = (L2 - 1) << 1;
swap(a + 1, a + N1);
}
int main(int argc, char *argv[]) {
assert(1 < argc);
int L = atoi(argv[1]);
G(L);
putchar('\n');
G1(L);
}
关于algorithm - Rutkowska 的位反转算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52226858/