7

经过反复试验，我找到了以下几行python代码，

for N in range(2**1,2**3):
    print [(2**n % (3*2**(2*N - n))) % (2**N-1) for n in range(2*N+1)]

产生以下输出，

[1, 2, 1, 2, 1]
[1, 2, 4, 1, 4, 2, 1]
[1, 2, 4, 8, 1, 8, 4, 2, 1]
[1, 2, 4, 8, 16, 1, 16, 8, 4, 2, 1]
[1, 2, 4, 8, 16, 32, 1, 32, 16, 8, 4, 2, 1]
[1, 2, 4, 8, 16, 32, 64, 1, 64, 32, 16, 8, 4, 2, 1]

即 2 到2**(N-1)1 的幂，并且 2 的幂相反。这正是我的问题所需要的（fft 和小波相关）。但是，我不太确定它为什么有效？我理解的最终模运算，它提供了系列中间的 1。第一个模运算中的因子 3 让我很头疼。任何人都可以提供解释吗？具体来说，我的基数 2 和因子 3 之间的关系是什么？

4

3 回答 3

13

首先，正如其他人所说，可能有更简单的实现，您可能应该使用这些。

但要回答你的问题，这就是你得到这个结果的原因：

当 n<N 时：

2 n % (3*2 2N-n ) = 2 n，因为 2 n < 3*2 2N-n。然后 2 n % (2 N -1) = 2 n，给出预期结果。

当 n=N 时：

2 N % (3*2 2N-N ) = 2 N和 2 N % (2 N -1) = 1。

当 N<n<=2N 时：

设 n = 2N - k。然后：

2 n % (3*2 2N-n ) = 2 2N-k % (3*2 k ) = 2 k *(2 2N-2k % 3) = 2 k * (4 N-k % 3)

4 的任何幂都等于 1 模 3（因为 4=1（模 3），所以 4 m =1 m =1（模 3）也是如此）。所以最终结果是 2 k = 2 2N-n，正如预期的那样。

使用其他号码：

如果您使用底数a而不是 2，使用数字b而不是 3，最后一部分将为您提供：

a k * ((a 2 ) Nk % b)

因此，您需要选择 b 为 a 2 -1 的任何因子，这将确保 ((a 2 ) Nk % b) = 1 对于任何 k。

于 2011-03-30T16:56:01.583 回答
6

虽然我和下一个极客一样喜欢聪明的解决方案，但如果您无法理解自己的代码，为什么不使用简单的解决方案呢？维护起来会容易得多，而且速度并不慢：

def fft_func(ex):
    if ex == 0:
        return [0, 0, 0]
    else:
        return [2**n for n in range(0, ex+1)] + [1] + [2**n for n in range(ex, -1, -1)]
于 2011-03-30T16:20:20.183 回答
1

生成该列表的更简单方法：

for N in range(2**1,2**3):
    print [2**((N-abs(N-k))%N) for k in range(2*N+1)]
于 2011-04-03T04:43:19.400 回答