Wie funktioniert diese Approximation der Division mit Bit-Shift-Operationen?

Question

In java.util.DualPivotQuicksort erscheint die folgende Codezeile:

// Inexpensive approximation of length/7 
int seventh = (length >> 3) + (length >> 6) + 1; 

Die Variable length ein int größer oder gleich 47 ist

Ich bin damit vertraut, wie die signierte rechte Shift-Operator funktioniert. Aber ich weiß nicht, warum diese speziellen Operationen zu einer Annäherung der Division um 7 führen. Könnte jemand bitte erklären?

Answer 1

>> ist Bitshift. Jedes Bit Sie rechts verschieben, in der Tat teilt die Anzahl der 2.

Daher (length >> 3) ist length/8 (abgerundet) und (length >> 6) ist length/64.

Nehmen (length/8)+(length/64) beträgt ca. length*(1/8+1/64) = length*0.140625 (ungefähr)

1/7 = 0.142857...

Die +1 am Ende für jeden Begriff in +0.5 aufgeteilt werden, so dass length/8 zum nächsten gerundet wird (statt nach unten), und length/64 wird auch auf den nächsten gerundet.

---

In der Regel können Sie einfach ungefähre 1/y, wo y = 2^n+-1 mit einer ähnlichen Bit-Shift-Annäherung.

Die unendliche geometrische Reihe ist:

1 + x + x^2 + x^3 + ... = 1/(1 - x) 

Multipliziert von x:

x + x^2 + x^3 + ... = x/(1 - x) 

Und x = 1/2^n

1/2^n + 1/2^2n + 1/2^3n + ... = (1/2^n)/(1 - 1/2^n) 
1/2^n + 1/2^2n + 1/2^3n + ... = (1/2^n)/((2^n - 1)/2^n) 

1/2^n + 1/2^2n + 1/2^3n + ... = 1/(2^n - 1) 

Substitution Dieser annähert y = 2^n - 1.

Um y = 2^n + 1 zu approximieren, ersetzen Sie stattdessen x = -1/2^n.

- 1/2^n + 1/2^2n - 1/2^3n + ... = (-1/2^n)/(1 + 1/2^n) 
1/2^n - 1/2^2n + 1/2^3n - ... = (1/2^n)/((2^n + 1)/2^n) 

1/2^n - 1/2^2n + 1/2^3n - ... = 1/(2^n + 1) 

Dann kürzen Sie einfach die unendliche Reihe auf die gewünschte Genauigkeit.

Answer 2

Um einen mathematischen Hintergrund zu ronalchn Antwort zu setzen:

Seit 7 = 8-1 = 8 * (1-1/8), durch die geometrische Reihe Division durch 7 ist das gleiche wie die Multiplikation mit

1/7 = 1/8 · (1 + 1/8 + 1/8² + 1/8³ + ...) = 1/8 + 1/8² + 1/+ ... 8³

---

Um das Gleiche für die Division durch 5 zu tun, würde man das verwenden 3 · 5 = 16-1 und somit

1/5 = 3/16 · (1 + 1/16 + 1/16² + ...)

, die eine Formel wie

(3*n)<<4 + (3*n) << 8 + 1 

Answer 3

Set x = 1/8 in der einladen Gleichheit bekannt

1 + x + x^2 + x^3 + ... = 1/(1 - x) 

und vereinfachen,

geben

1/8 + 1/64 + 1/512 + ... = 1/7 

Multiplizieren Sie beide Seiten von dieser durch length in Ihrem Beispiel

length/7 = length/8 + length/64 + length/512 + ... 

Hinweis zu geben, dass diese "exakte" Teilung ist, nicht Division integer - ich Mathematik ich schreibe, nicht Java-Code.

Dann geht die Approximation davon aus, dass der dritte und die folgenden Terme zu klein sind, um von Bedeutung zu sein, und dass im Durchschnitt einer der Werte length/8 und length/64 abgerundet werden muss. Also, jetzt unter Verwendung der Ganzzahldivision ist length/7 = length/8 + length/64 + 1 eine sehr gute Annäherung.

Der Ausdruck, den Sie mit bitweisen Operatoren gaben, ist nur eine alternative Möglichkeit, dies zu schreiben, vorausgesetzt, length ist positiv.

Answer 4

Computing alle Werte von

n/8 + n/64 - n/7 

der Fehler wächst linear, während negative bleiben.

Die folgende Liste zeigt das erste Mal ein gegebener Fehler

n = 7 e = -1 
n = 63 e = -2 
n = 511 e = -3 
n = 959 e = -4 
n = 1407 e = -5 
n = 1855 e = -6 
n = 2303 e = -7 
n = 2751 e = -8 
n = 3199 e = -9 
n = 3647 e = -10 
n = 4095 e = -11 
n = 4543 e = -12 
n = 4991 e = -13 
n = 5439 e = -14 
n = 5887 e = -15 
n = 6335 e = -16 
n = 6783 e = -17 
n = 7231 e = -18 
n = 7679 e = -19 
n = 8127 e = -20 
n = 8575 e = -21 
n = 9023 e = -22 
n = 9471 e = -23 
n = 9919 e = -24 
... 

Das Verhältnis offensichtlich dazu neigt, zu 1/448 = 1/8 + 1/64 - 1/7 erscheint.