Führen Sie Ganzzahldivision mit Multiplikation

Question

Mit Blick auf x86 Assembly von einem Compiler erzeugt, bemerkte ich, dass (vorzeichenlose) Ganzzahl Divisionen manchmal als ganzzahlige Multiplikationen implementiert sind. Diese Optimierungen scheinen der Form

value/n => (value * ((0xFFFFFFFF/n) + 1))/0x100000000 

Zum Beispiel zu folgen, eine Division durch 9 ausführen:

12345678/9 = (12345678 * 0x1C71C71D)/0x100000000 

Eine Division durch 3 verwenden würde Multiplikation mit 0x55555555 + 1, und so weiter.

Ausnutzen der Tatsache, dass die mul Anweisung den hohen Teil des Ergebnisses im edx Register speichert, kann das Endergebnis der Division mit einer einzigen Multiplikation mit einem magischen Wert erhalten werden. (Obwohl diese Optimierung manchmal in Verbindung mit einer bitweisen Verschiebung am Ende verwendet wird.)

Ich hätte gerne einen Einblick, wie das tatsächlich funktioniert. Wann ist dieser Ansatz gültig? Warum muss 1 zu unserer "magischen Zahl" hinzugefügt werden?

Answer 1

Diese Methode heißt "Division durch Invariante Multiplikation".

Die Konstanten, die Sie sehen, sind tatsächlich Annäherungen des Reziproken.

Also anstatt die Berechnung:

N/D = Q 

Sie etwas tun, wie diese statt:

N * (1/D) = Q 

wo 1/D ein reziprok ist, die vorberechnet werden kann.

Grundsätzlich sind Kehrwerte ungenau, es sei denn ist eine Zweierpotenz. Es wird also einen Rundungsfehler geben. Die +1, die Sie sehen, ist da, um den Rundungsfehler zu korrigieren.

---

Das häufigste Beispiel ist die Division durch 3:

N/3 = (N * 0xaaaaaaab) >> 33 

Wo 0xaaaaaaab = 2^33/3 + 1.

Dieser Ansatz wird auf andere Teiler verallgemeinert.