Durch viel Versuch und Irrtum fand ich die folgenden Zeilen des Python-Codes,
%Vor%welche die folgende Ausgabe erzeugen,
%Vor% d. Potenzen von 2 bis zu 2**(N-1) , 1, und die Potenzen von zwei umgekehrt. Genau das benötige ich für mein Problem (fft und wavelet). Ich bin mir allerdings nicht ganz sicher, warum es funktioniert? Die letzte Modulo-Operation, die ich verstehe, liefert die 1 in der Mitte der Serie. Der Faktor 3 in der ersten Modulo-Operation bereitet mir Kopfschmerzen. Kann jemand eine Erklärung anbieten? Insbesondere, was ist die Beziehung zwischen meiner Basis, 2, und dem Faktor 3?
Zuallererst, wie andere gesagt haben, gibt es viel einfachere Implementierungen, und Sie sollten diese wahrscheinlich verwenden.
Aber um Ihre Frage zu beantworten, hier ist, warum Sie dieses Ergebnis erhalten:
Wenn n & lt; N:
2 n % (3 · 2 <2N-n ) = 2 n , weil 2 n & lt; ; 3 * 2 2N-n . Dann ergibt 2 n % (2 N -1) = 2
Wenn n = N :
2 N % (3 · 2 <2N-N ) = 2
Wenn N & lt; n & lt; = 2N:
Sei n = 2N - k. Dann:
2 n % (3 · 2 2N-n ) = 2 2N-k % (3 · 2
Jede Potenz von 4 ist gleich 1 Modulo 3 (weil 4 = 1 (mod 3), also 4 m = 1 m = 1 (mod 3) als Gut). Das Endergebnis ist also wie erwartet 2 k = 2 2N-n
Andere Zahlen verwenden:
Wenn Sie die Basis a anstelle von 2 und die Zahl b anstelle von 3 verwenden, erhalten Sie im letzten Teil:
a k * ((a 2 ) N-k % b)
Sie müssten also b als einen beliebigen Faktor von 2 -1 wählen, um sicherzustellen, dass ((a 2 ) Nk % b) = 1 für jedes k.
Tags und Links python algorithm language-agnostic math number-theory