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 の累乗は、3 を法とする 1 に等しくなります (4=1 (mod 3) であるため、4 m =1 m =1 (mod 3) も同様です)。したがって、最終結果は予想どおり 2 k = 2 2N-nです。

他の番号を使用する:

2 の代わりに基数aを使用し、3 の代わりに数値bを使用すると、最後の部分は次のようになります。

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

したがって、任意の k に対して ((a 2 ) Nk % b) = 1となるように、b を a 2 -1の任意の因数として選択する必要があります。

于 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 に答える