Ich muss einen Code optimieren, wo ich einen Vektor von ints (32 Bit) mit einem skalaren Modulo p multipliziere (wobei p die Primzahl (2 ^ 32) -5 ist) und dann diesen Vektor von einem anderen Vektor modulo p subtrahiere .
Der Code sieht so aus:
%Vor%Ich verwende Longs, weil Java keine Ganzzahlen ohne Vorzeichen unterstützt, aber beide Vektoren mod p sind, so dass Sie erwarten können, dass jede Zahl 0 & lt; = x & lt; (2 ^ 32) -5
Irgendwelche Ideen, um das zu optimieren? Die Mod-P-Operation nimmt den größten Teil der Ausführungszeit in Anspruch, sodass eine Möglichkeit, dies zu optimieren, darin besteht, ModP nach der Multiplikation irgendwie nicht zu tun und dies erst nach der Subtraktion zu tun. Irgendwelche Ideen, wie man das macht?
Es ist möglich, die Berechnung zu beschleunigen und jegliche Division zu vermeiden, indem die Tatsache verwendet wird, dass 2 ^ 32 = 5 (mod p).
Teilen Sie nach der Multiplikation und Subtraktion das Ergebnis in niedrige (x% 2 ^ 32) und hi (x / 2 ^ 32) Teile. Dann multipliziere den Hi-Part mit 5 und summiere mit dem Low-Part. Wiederholen Sie diesen Vorgang noch einmal. Wenn das Ergebnis größer als p ist, p subtrahieren. Fügen Sie für ein negatives Ergebnis p.
hinzuEdit: Da kombinierte Multiplikation und Subtraktion überlaufen kann, sollte das Ergebnis der Multiplikation auch modulo p genommen werden. Aber nur ein Schritt der oben genannten Prozedur ist genug: Einfach teilen, mit 5 multiplizieren und hinzufügen.
Tags und Links java optimization performance primes modulo