Quelle meine Antwort in:

Ist dieser Ausdruck im C-Präprozessor korrekt?

Ich bin hier ein bisschen aus dem Ruder gelaufen und versuche zu verstehen, wie diese spezielle Optimierung funktioniert.

Wie in der Antwort erwähnt, optimiert gcc die Ganzzahldivision durch 7, um:

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

Was übersetzt zurück in C als:

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

Werfen wir einen Blick auf den ersten Teil:

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

Warum diese Nummer?

Nun, nehmen wir 2 ^ 64 und teilen es durch 7 und sehen, was herausspringt.

2^64 / 7 = 2635249153387078802.28571428571428571429

Das sieht nach einem Durcheinander aus, was ist, wenn wir es in ein Oktal umwandeln?

0222222222222222222222.22222222222222222222222

Das ist ein sehr hübsches Wiederholungsmuster, das kann doch kein Zufall sein. Ich meine, wir erinnern uns, dass 7 ist0b111 und wir wissen, dass wenn wir durch 99 teilen, wir dazu neigen, sich wiederholende Muster in Basis 10 zu erhalten. Es ist also sinnvoll, dass wir ein sich wiederholendes Muster in Basis 8 erhalten, wenn wir durch 7 teilen.

Woher kommt also unsere Nummer?

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

* 7 = 17179869189

Und schließlich ist 171798691842^34

Dies bedeutet, dass 17179869189 das nächste Vielfache von 7 2 ^ 34 ist. Oder anders ausgedrückt2454267027 ist die größte Zahl, die in a passtuint32_t was, wenn mit 7 multipliziert, einer Potenz von 2 sehr nahe kommt

Was ist diese Zahl im Oktal?

0222222222223

Warum ist das wichtig? Nun, wir wollen durch 7 teilen. Diese Zahl ist 2 ^ 34/7 ... ungefähr. Wenn wir also mit dieser Zahl multiplizieren und dann 34 Mal nach links schalten, sollten wir eine Zahl erhalten, die der genauen Zahl sehr nahe kommt.

Die letzten beiden Zeilen sehen so aus, als würden sie Approximationsfehler korrigieren.

Vielleicht kann jemand mit etwas mehr Wissen und / oder Erfahrung auf diesem Gebiet dazu beitragen.

>>> 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
... 

Fehler beginnen bei 3435973841, was lustig genug ist, 0b11001100110011001100110011010001

Die Klassifizierung, warum die Approximation fehlschlägt, ist mir ein bisschen unverständlich, und warum die Patches das Problem beheben, ist es auch. Weiß jemand, wie die Magie funktioniert, die über das hinausgeht, was ich hier niedergelegt habe?