为什么我得到这[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和wavelet相关).但是,我不太清楚为什么会这样？我理解的最终模运算,它提供了系列中间的1.第一个模运算中的因子3给我带来了麻烦.任何人都可以提供解释吗？具体来说,我的基数2和因子3之间的关系是什么？

Answer 1

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

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

当n <N时:

2 ⁿ%(3*2 ^2N-n)= 2 ⁿ,因为2 ⁿ <3*2 ^2N-n.然后2 ⁿ%(2 ^N -1)= 2 ⁿ,给出预期结果.

当n = N时:

2 ^Ñ%(3*2 ^2N-N)= 2 ^Ñ,和2 ^Ñ%(2 ^Ñ -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的幂等于1模3(因为4 = 1(模3),所以4 ^m = 1 ^m = 1(mod 3)).因此,最终结果是2 ^k = 2 ^2N-n,如预期的那样.

使用其他数字:

如果您使用基数a而不是2,而数字b而不是3,则最后一部分将为您提供:

a ^k*((a ²)^Nk%b)

所以你需要选择b为² -1的任何因子,这将确保任何k的((a ²)^Nk%b)= 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)]