Szybkie mnożenie i odejmowanie modulo a prime

Question

Potrzebuję zoptymalizować kod, w którym pomnożę wektor ints (32-bitowy) za pomocą skalarnego modulo p (gdzie p jest liczbą pierwszą (2^32) -5), a następnie odjąć ten wektor z innego wektora modulo p.

Kod wygląda następująco:

public static void multiplyAndSubtract(long fragmentCoefficient, long[] equationToSubtractFrom, long[] equationToSubtract) { 
    for (int i = 0; i < equationToSubtractFrom.length; i++) { 
     equationToSubtractFrom[i] = modP(equationToSubtractFrom[i] - multiplyModP(fragmentCoefficient, equationToSubtract[i])); 
    } 
} 

Używam tęskni ponieważ Java nie obsługuje liczb całkowitych, ale oba wektory są mod p więc można się spodziewać każdy numer wynosi 0 < = x < (2^32) -5

Wszelkie pomysły na optymalizację tego? Operacja mod p zajmuje większość czasu wykonania, więc jeden sposób optymalizacji tego może w jakiś sposób nie spowodować modP po mnożeniu i zrobić to dopiero po odjęciu. Wszelkie pomysły, jak to zrobić?

Answer 1

Możliwe jest przyspieszenie obliczeń i uniknięcie podziału w ogóle za pomocą faktu, że 2^32 = 5 (mod p).

Po pomnożeniu i odjęciu, podziel wynik na niskie (x% 2^32) i cześć (x/2^32) części. Następnie pomnóż część hi do 5 i podsumuj małą częścią. Następnie powtórz tę procedurę jeszcze raz. Jeśli wynik jest większy niż p, odejmij p. Aby uzyskać wynik ujemny, dodaj p.

Edycja: Ponieważ kombinowane mnożenie i odejmowanie może się przepełnić, wynik mnożenia również powinien zostać przyjęty modulo p. Wystarczy jednak tylko jeden krok powyższej procedury: wystarczy podzielić, pomnożyć do 5 i dodać.

Answer 2

e - (f * e mod p) mod p = (e-e f) mod p 

Zobacz Wolfram Alpha.

Answer 3

Znam dwa sposoby, aby to zrobić bez używania podziału lub moduł:

metoda 1: Inwariant mnożenie. (see this paper)

Podstawową ideą tutaj jest wstępne obliczenie i przybliżenie odwrotności wartości p, która pozwala na podział liczb całkowitych za pomocą tylko kilku wielokrotności całkowitych. Następnie możesz pomnożyć i uzyskać swój moduł. To jest łatwiejsze podejście do wdrożenia.

Metoda 2: (ten, który zwykle używam), jest użycie zmiennoprzecinkowych. Konwertuj liczby na zmiennoprzecinkowe i mnożąc przez wstępnie obliczoną odwrotność p. Następnie zaokrąglij i przekonwertuj z powrotem na liczbę całkowitą. Takie podejście jest trudniejsze do uzyskania, ale z mojego doświadczenia wynika, że ​​jest ono szybsze, jeśli zostanie wykonane prawidłowo.

Oba podejścia nie obejmują żadnych podziałów poza wstępnym obliczeniem wzajemności w liczbie całkowitej lub zmiennoprzecinkowej.

Niezależnie od tego, czy któraś z tych metod będzie szybsza niż prosta metoda użycia %, będzie zależeć od tego, jak dobrze można je wdrożyć. Nie mogę więc zagwarantować, że jeden z nich będzie szybszy.