Integer Division durch 7

Question

Quelle meiner Antwort in:

Is this expression correct in C preprocessor

Ich bin ein wenig aus meinem forten hier, und ich versuche, wie dieses besondere Optimierung Werke zu verstehen.

Wie in der Antwort erwähnt, gcc Integer-Division von 7 optimieren:

mov edx, -1840700269 
mov eax, edi 
imul edx 
lea eax, [rdx+rdi] 
sar eax, 2 
sar edi, 31 
sub eax, edi 

Welche zurück in C übersetzt:

int32_t divideBySeven(int32_t num) { 
    int32_t temp = ((int64_t)num * -015555555555) >> 32; 
    temp = (temp + num) >> 2; 
    return (temp - (num >> 31)); 
} 

Schauen wir uns den ersten Teil einen Blick:

int32_t temp = ((int64_t)num * -015555555555) >> 32; 

Warum diese Nummer?

Na, mal 2 nehmen^64 und teilen sie durch 7 und sehen, was herausspringt.

2^64/7 = 2635249153387078802.28571428571428571429 

Das sieht wie ein Durcheinander aus, was, wenn wir es in octal umwandeln?

0222222222222222222222.22222222222222222222222 

Das ist ein sehr schönes sich wiederholendes Muster, das kann sicherlich kein Zufall sein. Ich meine, wir nicht vergessen, dass 7 0b111 ist und wir wissen, dass, wenn wir durch 99 teilen wir Muster in der Basis zu bekommen neigen zu wiederholen 10. So ist es sinnvoll, dass wir ein sich wiederholendes Muster in der Basis 8 erhalten würde, wenn wir von 7.

teilen

Woher kommt unsere Nummer?

(int32_t)-1840700269 ist die gleiche wie (uint_32t)2454267027

* 7 = 17179869189

Und schließlich ist 17179869184 2^34

was bedeutet, dass 17179869189 das nächste Vielfache von 2^7 34 ist. Oder um es anders auszudrücken 2454267027 ist die größte Zahl, die in einem uint32_t passen, die, wenn multipliziert mit 7 ist sehr nah an eine Potenz von 2

Was in Oktal diese Zahl ist?

0222222222223 

Warum ist das wichtig? Nun, wir wollen durch 7 teilen. Diese Zahl ist 2^34/7 ... ungefähr. Wenn wir also 34 mal mit leftshift multiplizieren, sollten wir eine Zahl erhalten, die der genauen Zahl sehr nahe kommt.

die letzten beiden Zeilen schauen, wie sie zu flicken Approximationsfehler entworfen wurden.

Vielleicht hat jemand mit einem wenig mehr Wissen und/oder Know-how in diesem Bereich kann auf diese läutet.

>>> magic = 2454267027 
>>> def div7(a): 
... if (int(magic * a >> 34) != a // 7): 
...  return 0 
... return 1 
... 
>>> for a in xrange(2**31, 2**32): 
... if (not div7(a)): 
...  print "%s fails" % a 
... 

Ausfälle beginnen bei 3435973841 was komischerweise 0b11001100110011001100110011010001

Klassifizieren, warum die Annäherung ein bisschen über mich versagt ist, und warum die Patches es reparieren ist als gut.Weiß jemand, wie die Magie über das hinaus wirkt, was ich hier niedergelegt habe?

Answer 1

Der erste Teil des Algorithmus multipliziert mit einer Annäherung an den Reziprokwert von 7. In diesem Fall nähern wir uns der Berechnung des Reziproken mit einer ganzzahligen Multiplikation und einer rechten Bitverschiebung.

Zuerst sehen wir den Wert -1840700269 (oktal -015555555555) als eine 32-Bit-Ganzzahl. Wenn Sie dies als vorzeichenlose 32-Bit-Ganzzahl lesen, hat sie den Wert 2454267027 (oktal 22222222223). Es stellt sich heraus, dass 2454267027/2^34 eine sehr enge ganzzahlige Annäherung an 1/7 ist.

Warum wählen wir diese Zahl und diese besondere Stärke von 2? Je größer die von uns verwendeten Ganzzahlen sind, desto näher ist die Approximation. In diesem Fall scheint 2454267027 die größte Ganzzahl zu sein (die die obige Eigenschaft erfüllt), mit der Sie einen 32-Bit-int-Wert mit Vorzeichen multiplizieren können, ohne dass ein 64-Bit-int überläuft.

Als nächstes, wenn wir sofort mit >> 34 rechts verschieben und speichern das Ergebnis in einem 32-Bit-Int, verlieren wir die Genauigkeit in den zwei Bits niedrigster Ordnung. Diese Bits sind notwendig, um den richtigen Boden für eine ganzzahlige Division zu bestimmen.

Ich bin nicht sicher, dass die zweite Zeile korrekt aus dem x86-Code übersetzt wurde. An diesem Punkt, temp ist ungefähr num * 4/7, so num * 4/7 + num zu diesem und Bit-Verschiebung wird Ihnen etwa num * 1/7 + num * 1/4, ein ziemlich großer Fehler geben.

Nehmen Sie zum Beispiel als Eingabe 57, wo 57 // 7 = 8. Ich überprüfte die unten in Code auch:

• 57 * 2454267027 = 139893220539
• 139893220539 >> 32 = 32 (ca. 57 * 4/7 = 32.5714... an dieser Stelle)
• 32 + 57 = 89
• 89 >> 2 = 22
(huh ?? Nowhere der Nähe von 8 an dieser Stelle.)

Wie auch immer, für die letzte Zeile ist es eine Anpassung, die wir nach der Berechnung vorzeichenbehafteter ganzzahliger Division auf diese Weise vornehmen. Ich zitiere aus dem Abschnitt von Freude der Hacker auf unterzeichnet Division:

Der Code am natürlichsten berechnet den Boden Divisionsergebnis, also müssen wir eine Korrektur, um es der herkömmlichen Richtung 0 Ergebnis abgeschnitten machen zu berechnen. Dies kann mit drei Berechnungsanweisungen gemacht werden, indem zu der Dividende addiert wird, wenn die Dividende negativ ist.

In diesem Fall (in Bezug auf Ihre andere post) es scheint, dass Sie eine signierte Verschiebung tun, so wird es -1 im Fall einer negativen Zahl subtrahieren; mit dem Ergebnis +1.

Dies ist noch nicht alles, was Sie tun können; Hier ist ein noch verrückter blog post about how to divide by 7 with just a single multiplication.