Почему я получил это [1, 2, 4, 8, 16, 1, 16, 8, 4, 2, 1]? - PullRequest
Новая
       45

Почему я получил это [1, 2, 4, 8, 16, 1, 16, 8, 4, 2, 1]?

7 голосов
/ 30 марта 2011

Путем множества проб и ошибок я обнаружил следующие строки кода 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, и полномочия двух поменялись местами.Это именно то, что мне нужно для моей проблемы (FFT и вейвлет, связанные).Тем не менее, я не совсем уверен, , почему это работает?Заключительная операция по модулю, я понимаю, она обеспечивает 1 в середине серии.Фактор 3 в первой операции по модулю вызывает у меня головную боль.Кто-нибудь может предложить объяснение?В частности, какова связь между моей базой, 2, и фактором, 3?

Ответы [ 3 ]

13 голосов
/ 30 марта 2011

Прежде всего, как уже говорили другие, возможны гораздо более простые реализации, и вы, вероятно, должны их использовать.

Но чтобы ответить на ваш вопрос, вот почему вы получаете этот результат:

Когда n

2 n % (3 * 2 2N-n ) = 2 n , потому что 2 n <3 * 2 <sup>2N-н . Тогда 2 n % (2 N -1) = 2 n , что дает ожидаемый результат.

Когда n = N :

2 N % (3 * 2 2N-N ) = 2 N и 2 N % (2 * 1039) * N -1) = 1.

Когда N

Пусть n = 2N - k. Тогда:

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

Любая степень 4 равна 1 по модулю 3 (потому что 4 = 1 (мод 3), поэтому 4 м = 1 м = 1 (мод 3)) , Таким образом, окончательный результат равен 2 k = 2 2N-n , как и ожидалось.

Использование других номеров:

Если вы используете основание a вместо 2 и число b вместо 3, последняя часть даст вам:

a k * ((a 2 ) N-k % b)

Таким образом, вам нужно выбрать b, чтобы быть любым фактором, равным 2 -1, который обеспечит ((a 2 ) Nk % б) = 1 для любого k.

6 голосов
/ 30 марта 2011

Хотя я люблю умные решения так же, как и следующего гика, почему бы вам не использовать простое решение, если у вас возникают проблемы с пониманием собственного кода?Его будет намного проще поддерживать, и он не будет медленнее: 

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)]
1 голос
/ 03 апреля 2011

Более простой способ составить этот список: 

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