Der schnellste Weg, eine 128-Bit-Ganzzahl modulo einer 64-Bit-Ganzzahl zu berechnen

Lesezeit: 7 Minuten

Benutzer200783

Ich habe eine 128-Bit-Ganzzahl ohne Vorzeichen A und eine 64-Bit-Ganzzahl ohne Vorzeichen B. Wie kann ich am schnellsten berechnen? A % B – das ist der (64-Bit) Rest aus der Division von A durch B?

Ich möchte dies entweder in C oder in der Assemblersprache tun, aber ich muss auf die 32-Bit-x86-Plattform abzielen. Dies bedeutet leider, dass ich weder die Compiler-Unterstützung für 128-Bit-Ganzzahlen noch die Fähigkeit der x64-Architektur nutzen kann, die erforderliche Operation in einer einzigen Anweisung auszuführen.

Bearbeiten:

Vielen Dank für die bisherigen Antworten. Es scheint mir jedoch, dass die vorgeschlagenen Algorithmen ziemlich langsam wären – wäre nicht der schnellste Weg, eine 128-Bit-mal-64-Bit-Division durchzuführen, die Nutzung der nativen Unterstützung des Prozessors für die 64-Bit-mal-32-Bit-Division? Weiß jemand, ob es eine Möglichkeit gibt, die größere Division in Bezug auf ein paar kleinere Divisionen durchzuführen?

Re: Wie oft ändert sich B?

In erster Linie interessiert mich eine allgemeine Lösung – welche Berechnung würden Sie durchführen, wenn A und B wahrscheinlich jedes Mal anders sind?

Eine zweite mögliche Situation ist jedoch, dass B nicht so oft variiert wie A – es können bis zu 200 As durch jedes B geteilt werden. Wie würde sich Ihre Antwort in diesem Fall unterscheiden?

Wie oft ändert sich B?

– Benutzer287792

4. April 2010 um 16:28 Uhr
Wie schnell muss funktionieren? Wie viele 128 mal 64 Modulo-Operationen pro Sekunde erwarten Sie?

– GJ.

10. April 2010 um 18:09 Uhr
Der Russian Peasant-Algorithmus ist einfach, verwendet jedoch Schleifen und nutzt die Divisionsanweisung in x86 nicht aus. Sie können den Algorithmus hier verwenden, es handelt sich um eine 64/32-Bit-Division durch 32/16-Bit-Dividierungsbefehl, aber Sie können ihn auf 128/64-Bit mal 64/32-Bit verdoppeln

– phuklv

29. Januar 2014 um 2:57 Uhr
Sollten Antworten ihren Code testen wollen, steht diese Wiki-Antwort zur Verfügung.

– chux – Wiedereinsetzung von Monica

22. September 2016 um 18:47 Uhr

Code hat Fehler. Interessant, dass es nicht gemeldet wurde 6 Jahre. Versuchen A=2, B=1 geht in die Endlosschleife. 0x8711dd11 mod 0x4388ee88 schlägt fehl (Ergebnis s/b 1, nicht 0x21c47745) sowie andere. Empfehlen while (X < A/2) –> while (X <= A/2) zu reparieren. Ihr Pseudocode wie getestet unsigned cafMod(unsigned A, unsigned B) { assert(B); unsigned X = B; while (X < A / 2) { X <<= 1; } while (A >= B) { if (A >= X) A -= X; X >>= 1; } return A; }

– chux – Wiedereinsetzung von Monica

31. August 2016 um 18:49 Uhr
@chux: Du hast vollkommen recht, behoben. Es wurde wahrscheinlich nicht früher gemeldet, weil es nur passiert, wenn A = 2ⁿ B oder A = 2ⁿ B + 1 ist. Danke!

– Café

1. September 2016 um 1:13 Uhr
Yup, in x86-asm-Implementierung x<<=1 wie add lo,lo/adc mid,mid/… ist effizienter als shl lo/rcl mid,1/… Aber in C sollte das der Compiler für Sie erledigen. Natürlich in x86 asm, sollten Sie eigentlich verwenden bsr (Bit-Scan) oder lzcnt (Zählung der führenden Null), um die Position des höchsten gesetzten Bits zu finden, und verwenden Sie dann shld hi, mid2, cl / … / shl low, cl um alle Verschiebungen in einem Schritt durchzuführen, anstatt dafür zuerst zu loopen while (x <= A/2) Schleife. Im 32-Bit-Modus ist die Verwendung von SSE2 für XMM-SIMD-Verschiebungen mit 64-Bit-Elementen verlockend, insbesondere um die Verzweigung für führende Nullen >= 32 zu reduzieren

– Peter Cordes

17. Juli 2019 um 14:52 Uhr

Danke, ich glaube, ich verstehe, wie die auf sputsoft.com beschriebenen Algorithmen auf diese Situation angewendet werden. AFAICT, Algorithmus G zeigt, wie eine mb-Bit-mal-nb-Bit-Division als eine Reihe von m-n+1 (n+1)b-Bit-mal-nb-Bit-Divisionen durchgeführt wird, wobei b die Anzahl der Bits pro Ziffer ist. Der Algorithmus Q zeigt dann, wie jede dieser (n+1)b-Bit-mal-nb-Bit-Teilungen als eine einzelne 2b-Bit-mal-b-Bit-Teilung durchzuführen ist. Da die größte Dividende, die wir verarbeiten können, 64-Bit ist, müssen wir b = 32 festlegen. Die Algorithmen zerlegen somit unsere 128-Bit mal 64-Bit-Division (m = 4, n = 2) in 3 64-Bit mal 32-Bit-Divisionen. Klingt das genau?

– Benutzer200783

10. April 2010 um 12:40 Uhr
Ich kann sagen, dass Sie sich bereits eingehendere Gedanken über die Algorithmen gemacht haben als ich, als ich meine Antwort gepostet habe, daher kann ich nicht sicher sagen, ob Ihre endgültige Anzahl von Divisionsoperationen richtig ist. Ich denke jedoch, dass Sie die Grundidee haben, wie Sie vorgehen müssen.

– Dale Hagglund

10. April 2010 um 14:36 Uhr
Ein weiterer Gedanke: Sie sollten 16-Bit-Ziffern in Betracht ziehen, wenn Sie in C schreiben und daher keinen direkten Zugriff auf 32b x 32b -> 64b-Multiplikationsanweisungen haben oder Ihre 32-Bit-Ziffern nicht einbetten möchten eine 64-Bit-Ganzzahl und verwenden Sie die eigene integrierte 64-Bit-Arithmetik des Compilers. Ich kann mir keinen triftigen Grund vorstellen, letzteres zu vermeiden, aber Sie sollten sich vielleicht den generierten Assembler-Code dafür ansehen, wenn Sie wirklich, wirklich, wirklich um Geschwindigkeit besorgt sind.

– Dale Hagglund

10. April 2010 um 14:42 Uhr
Dieser Sputsoft-Link scheint jetzt ungültig zu sein. Nicht sicher warum – die Seite ist immer noch da. Diese Seite scheint verbunden zu sein, indem die kanooth-numbers Bibliothek wurde einmal genannt sputsoftnumbers.

– Craig McQueen

4. September 2013 um 4:50 Uhr
Die sputsoft-Seite befindet sich jetzt hier: janmr.com/blog/2009/08/…

– Cheng Sonne

30. Juli 2017 um 20:53 Uhr

@GJ, wenn der Compiler 64-Bit-Ganzzahlen unterstützt, ist es einfacher, nur die Mod-Operation für 64-Bit-Ganzzahlen zu verwenden. Die Methode von caf wird von MSVC ohnehin für 32-Bit-x86 verwendet, basierend auf meiner flüchtigen Bewertung der Assembly. Es enthält auch eine Optimierung für Dividenden unter 2^32. Sie könnten es also entweder selbst codieren oder einfach die vorhandene Compiler-Unterstützung verwenden.

– MSN

5. April 2010 um 16:21 Uhr
Ich bin mir nicht sicher, ob ich verstehe, wie das funktioniert. B ist 64-Bit, also sind (AH % B) und ((2^64 – B) % B)) beide 64-Bit. Wird die Multiplikation dieser beiden nicht eine 128-Bit-Zahl ergeben, sodass wir immer noch ein 128-Bit-mal-64-Bit-Modulo ausführen müssen?

– Benutzer200783

10. April 2010 um 12:54 Uhr
Vielen Dank für die Idee, sich anzusehen, wie Compiler 64-Bit-mal-64-Bit-Modulo auf x86 implementieren. Soweit ich das beurteilen kann, verwenden weder GCC (die Funktion __udivmoddi4 in libgcc2.c) noch MSVC (siehe ullrem.asm für die unsignierte Version) die “Russian Peasant”-Methode von caf. Stattdessen scheinen beide eine Variation des Algorithmus Q in dem von Dale Hagglund bereitgestellten Link (mit n = 2, b = 32) zu verwenden – die Annäherung an die 64-Bit-mal-64-Bit-Division mit einer 64-Bit-mal-32-Bit-Division , und nehmen Sie dann eine leichte Anpassung vor, um das Ergebnis bei Bedarf zu korrigieren.

– Benutzer200783

10. April 2010 um 14:02 Uhr
Problem bei diesem Ansatz: Die * Die Multiplikation benötigt ein 128-Bit-Ergebnis, das den letzten Schritt macht some_128_bit_positive_value % some_128_bit_positive_value und wir sind wieder da, wo wir angefangen haben. Versuchen Sie 0x8000_0000_0000_0000_0000_0000_0000_0000 mod 0xFFFF_FFFF_FFFF_FFFE. Ich würde sagen, die Antwort sollte 2 sein, aber Ihr Algorithmus gibt 0 aus (vorausgesetzt, das Produkt Ihrer Multiplikation ist Modulo 64-Bit). Dieser Code funktioniert für “128-Bit-Ganzzahl modulo eine 32-Bit-Ganzzahl”. Vielleicht ist mein Test falsch, aber ich würde gerne das Ergebnis Ihres Tests wissen.

– chux – Wiedereinsetzung von Monica

31. August 2016 um 20:01 Uhr
@chux: Ich stimme zu, dass die Antwort lauten sollte 2 zum 0x80000000000000000000000000000000 % 0xFFFFFFFFFFFFFFFE. Ich habe es in getestet calcder cmdline-Rechner mit beliebiger Genauigkeit. Ich habe bestätigt, dass das Abschneiden auf 64 Bit (mit einem bitweisen UND mit (2 ^ 64-1)) die Formel bricht, sodass Sie im Wesentlichen auf Quadrat 1 bleiben. (((AH % B) * ((2^64 - B) % B))&(2^64-1) + (AL % B))&(2^64-1) % B == 0 aber (((AH % B) * ((2^64 - B) % B)) + (AL % B)) % B == 2. ich benutzte AH=A>>64 und AL=0.

– Peter Cordes

1. September 2016 um 9:01 Uhr

Ich denke, deine Überlegungen sind mehr oder weniger richtig. Ja, die Idee, x87-Gleitkommadivision mit doppelter Genauigkeit zu verwenden, ist auch bekannt, aber x87 unterstützt nur die 63-Bit-Division, da das 64. Bit für das Mantissenzeichen reserviert ist, gemäß: IEEE-Standard 754 für binäre Gleitkommaarithmetik.

– GJ.

11. April 2010 um 7:03 Uhr
Ich sprach über das von x87 unterstützte Double-Extended-Format. Im Double-Format ist der Bruch nur 53 Bit lang. Im erweiterten ist der Bruch bzw. die Mantisse 64 Bit lang. Es gibt einen Unterschied zwischen diesem Format und den kleineren. Im erweiterten Format ist das führende Bit des Signifikanten im Gegensatz zu Doppel- oder Einzelzeichen explizit, aber ich glaube nicht, dass es sich viel ändert. In diesem Format sollten exakt 64-Bit-Ganzzahlen gespeichert werden können. Das Vorzeichen wird im erweiterten Format in Bit 79 gespeichert.

– Maciej Hehl

11. April 2010 um 10:55 Uhr
Ich habe den IEEE-Standard überprüft und Sie haben Recht. Das Mantisa-Zeichen wird im letzten Byte gespeichert.

– GJ.

11. April 2010 um 16:13 Uhr
Was Sie beschreiben, ist die sogenannte Basisfallteilung, wie sie von Knuth in seinem Algorithmus D (TAOCP Vol. 2) beschrieben wird. Es beruht auf der Tatsache, dass, wenn Sie die obersten zwei “Ziffern” des Dividenden durch die oberste Ziffer des Divisors dividieren, das Ergebnis höchstens um 2 abweicht. Sie testen dies, indem Sie das Ergebnis * Divisor vom Dividenden/Rest subtrahieren und mal sehen ob es negativ ist. Wenn ja, addierst du den Divisor und korrigierst den Quotienten, bis der Rest wieder positiv ist. Dann schleifen Sie für die nächstniedrigere Ziffer usw.

– Rudy Velthuis

14. März 2013 um 12:30 Uhr
Zustimmen (((AH % B) * ((2^64 - B) % B)) + (AL % B)) % B hat Probleme

– chux – Wiedereinsetzung von Monica

31. August 2016 um 20:03 Uhr

14111300cookie-checkDer schnellste Weg, eine 128-Bit-Ganzzahl modulo einer 64-Bit-Ganzzahl zu berechnen

#Algorithmus #c++ #modulo #Montage #x86