Rechnen (a * b) mod c schnell für c = 2^N + -1

Question

In 32-Bit-Integer-Mathematik, grundlegende mathematische Operationen von add und multiplizieren implizit mod 2^32 berechnet, was bedeutet, dass Ihre Ergebnisse die niedrigste Reihenfolge sein wird Bits addieren oder multiplizieren.

Wenn Sie das Ergebnis mit einem anderen Modulo berechnen möchten, könnten Sie sicherlich eine beliebige Anzahl von BigInt-Klassen in verschiedenen Sprachen verwenden. Und für Werte a, b, c < 2^32 könnten Sie die Zwischenwerte in 64 Bit langen Ints berechnen und integrierte% Operatoren verwenden, um nach rechts zu verkleinern.

Aber mir wurde gesagt, dass es spezielle Tricks gibt zum effizienten Berechnen von a * b mod C, wenn C die Form (2^N) -1 oder (2^N) +1 hat, die keine 64-Bit-Mathematik oder eine BigInt-Bibliothek verwenden und ziemlich effizient sind, mehr als eine willkürliche Modul-Bewertung, und auch richtig berechnen Fällen, die normalerweise ein 32-Bit-Int überlaufen würden, wenn Sie die Zwischen-Multiplikation enthalten.

Leider habe ich trotz der Tatsache, dass solche Spezialfälle eine schnelle Auswertungsmethode haben, keine Beschreibung der Methode gefunden. "Ist das nicht in Knuth?" "Ist das nicht irgendwo auf Wikipedia?" sind die Murmeltiere, die ich gehört habe.

Es ist anscheinend eine allgemeine Technik in Zufallszahlengeneratoren, die Multiplikationen von a * b Mod 2147483647 machen, da 2147483647 eine Primzahl gleich 2^31 -1 ist.

Also werde ich die Experten fragen. Was ist das für eine clevere Sonderfall-Multiply-mit-Mod-Methode, über die ich keine Diskussion habe?

Answer 1

Ich denke, der Trick ist folgendes (ich es in der Basis 10 tun werde, weil es einfacher ist, aber das Prinzip halten sollte)

Angenommen, Sie a*b mod 10000-1 multiplizieren und

a = 1234 = 12 * 100 + 34 
b = 5432 = 54 * 100 + 32 

jetzt a*b = 12 * 54 * 10000 + 34 * 54 * 100 + 12 * 32 * 100 + 34 * 32

12 * 54 * 10000 = 648 * 10000 
34 * 54 * 100 = 1836 * 100 
12 * 32 * 100 = 384 * 100 
34 * 32   = 1088 

Seit x * 10000 ≡ x (mod 10000-1) [1], t Die ersten und letzten Begriffe werden 648 + 1088. Der zweite und der dritte Terminus sind die "Tricks".Beachten Sie, dass:

1836 = 18 * 100 + 36 
1836 * 100 ≡ 18 * 10000 + 3600 ≡ 3618 (mod 10000-1). 

Dies ist im Wesentlichen eine zirkuläre Verschiebung. Geben Sie die Ergebnisse von 648 + 3618 + 8403 + 1088. Und beachten Sie, dass in allen Fällen die multiplizierten Zahlen sind < 10000 (seit < 100 und b < 100), so dass dies berechenbar ist, wenn Sie nur mehrere 2-stellige Zahlen zusammen und füge sie hinzu.

Im Binärformat wird es ähnlich funktionieren.

Beginnen Sie mit a und b, beide sind 32 Bits. Angenommen, Sie möchten sie mit mod 2^31 - 1 multiplizieren, aber Sie haben nur einen 16-Bit-Multiplikator (mit 32 Bits). Der Algorithmus wäre so etwas wie:

a = 0x12345678 
b = 0xfedbca98 
accumulator = 0 
for (x = 0; x < 32; x += 16) 
    for (y = 0; y < 32; y += 16) 
     // do the multiplication, 16-bit * 16-bit = 32-bit 
     temp = ((a >> x) & 0xFFFF) * ((b >> y) & 0xFFFF) 

     // add the bits to the accumulator, shifting over the right amount 
     total_bits_shifted = x + y 
     for (bits = 0; bits < total_bits_shifted + 32; bits += 31) 
      accumulator += (temp >> (bits - total_bits_shifted)) & 0x7FFFFFFF 

     // do modulus if it overflows 
     if (accumulator > 0x7FFFFFFFF) 
      accumulator = (accumulator >> 31) + (accumulator & 0x7FFFFFFF); 

Es ist spät, so dass der Akku Teil davon wird wahrscheinlich nicht funktionieren. Ich denke im Prinzip ist es aber richtig. Jemand kann das gerne bearbeiten, um es richtig zu machen.

Abgerollt, das ist auch ziemlich schnell, das ist was die PRNG verwenden, schätze ich.

[1]: x*10000 ≡ x*(9999+1) ≡ 9999*x + x ≡ x (mod 9999)

Answer 2

Eine schnelle Suche ergab diese: http://home.pipeline.com/~hbaker1/AB-mod-N.pdf. Leider ist es zu spät für mich, genug Sinn zu haben, um einfach in die vereinfachte Formel zu schreiben, aber es ist wahrscheinlich irgendwo in dieser Zeitung.

Answer 3

Angenommen, Sie können a * b als p*2^N+q berechnen. Dies kann 64-Bit-Berechnungen erfordern, oder Sie können a und b in 16-Bit-Teile aufteilen und auf 32-Bit berechnen.

Dann a*b mod 2^N-1 = p+q mod 2^N-1 seit 2^N mod 2^N-1 = 1.

Und a*b mod 2^N+1 = -p+q mod 2^N+1 seit 2^N mod 2^N+1 = -1. In beiden Fällen gibt es keine Unterteilung nach 2^N-1 oder 2^N+1.

Answer 4

Anstatt modulare Reduktion bei jedem Schritt zu tun, können Sie Montgomery reduction verwenden (es gibt andere descriptions), um die Kosten der modularen Multiplikationsberechnung zu reduzieren. Dies verwendet jedoch immer noch nicht die Eigenschaften von N plus/minus einer Zweierpotenz.

Answer 5

Die Identität Sie suchen sind, ist x mod N = (x mod 2^q)- c*floor(x/2^q), da N = 2^q + c und c eine ganze Zahl (aber typisch ± 1).

Möglicherweise möchten Sie Abschnitt 9.2.3 lesen: "Moduli von Sonderform" in "Primzahlen: A Computational Perspective" von Richard Crandall und Carl Pomerance. Neben der Theorie enthält es Pseudocode für einen Algorithmus, der die obige Beziehung implementiert.

Answer 6

Ich habe eine rather extensive page zu diesem Thema gefunden, diskutieren nicht nur den Algorithmus, sondern auch die spezifische Geschichte des Problems und der Lösung und die Möglichkeiten, die Menschen die Lösung verwendet haben.