我为什么会得到这个 [1, 2, 4, 8, 16, 1, 16, 8, 4, 2, 1]?

Question

经过多次尝试和错误，我找到了以下几行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之间有什么关系？

Answer 1

有一个更简单的方法来生成那个列表：

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

Answer 2

虽然我和其他技术爱好者一样喜欢聪明的解决方案，但如果你发现自己对代码理解有困难，为什么不试试简单的解决办法呢？这样会更容易维护，而且其实速度也不会慢多少。

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)]

Answer 3

首先，正如其他人所说的，其实有更简单的方法可以实现这个功能，你可能应该考虑使用这些更简单的方式。

不过为了回答你的问题，下面是你得到这个结果的原因：

当 n 小于 N 时：

2ⁿ % (3*2^2N-n) = 2ⁿ，因为 2ⁿ 小于 3*2^2N-n。接着 2ⁿ % (2^N-1) = 2ⁿ，所以得到了预期的结果。

当 n 等于 N 时：

2^N % (3*2^2N-N) = 2^N，而 2^N % (2^N-1) = 1。

当 N 小于 n 小于等于 2N 时：

假设 n = 2N - k。那么：

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

任何 4 的幂在模 3 下都等于 1（因为 4=1（模 3），所以 4^m=1^m=1（模 3）也是成立的）。所以最后的结果是 2^k = 2^2N-n，这也是预期的结果。

使用其他数字：

如果你用基数 a 代替 2，用数字 b 代替 3，那么最后的部分会变成：

a^k * ((a²)^N-k % b)

所以你需要选择 b 为 a²-1 的任何因子，这样可以确保 ((a²)^N-k % b) = 1 对于任何 k 都成立。