Modulo -Algorithmus: übersetzng von pseudocode

[Michael II]

Hallo Sequitar

falls ich deinen Code richtig lese (kompilieren kann ich ihn nicht und ich habe gerade weder Zeit noch ...), dann berechnest du den Vektor T bei jedem Aufruf von Tmod.quickmod() neu.

In den beiden Fällen 1. "X < Y" und 2. "bitlength(X) = k" benötigst du T nicht => nicht berechnen.

Ziel des Algos ist es, teure Divisionen durch "billige" Additionen zu ersetzen. Wenn du zur Ermittlung des Funktionswerts von Tmod.quickmod(X,Y) bitlength(Y) Mal Math.Modulo(Result, Y) aufrufst, wirkst du diesem Ziel (je nach Implementation von Math.Modulo) u.U. entgegen. [ Wenn du Tmod.quickmod(X,Y):=Math.Modulo(X, Y) setzen würdest, hättest du ja nur einen einzigen Math.Modulo() Aufruf und gleich noch das Resultat von Tmod.quickmod() [wobei man für eine genaue Bewertung die Bit-Längen von x und y und die Implementierung von Math.Modulo kennen muss].
Du müsstest prüfen, wie schnell deine Kombi aus Bitshift und Math.Modulo die bitlength(Y) Werte von T berechnet. (Wenn Y k:=bitlength(Y) Bit breit ist, blähst du mit deiner Bitshift Funktion Y auf bis zu 2*k-1 Bit Werte auf - muss das sein (?)) => evt. T anders berechnen.

Wenn du Tmod.quickmod(X,Y) für mehrere (x,y) berechnest und der Wert y dabei gleich bleibt, dann lohnt es sich (je nach Umgebung) die Werte von T abzuspeichern (T ist ja nur abgängig von y). Dies wird im Paper breit diskutiert. Der Algo ist genau in diesem Fall (mehrere quickmod() Berechnungen, y immer gleich) besonders effektiv (nur noch Additionen). Diesen Teil sehe ich in deinem Code noch nicht umgesetzt.