Jak działa ta aproksymacja podziału za pomocą operacji zmiany bitowej?

Question

W java.util.DualPivotQuicksort następujący wiersz kodu pojawia:

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

Zmienna length jest int większa lub równa 47.

znam jak działa operator podpisał prawy shift. Ale nie wiem, dlaczego te konkretne operacje skutkują przybliżeniem podziału o 7. Czy ktoś mógłby wyjaśnić, proszę?

Answer 1

>> to bitshift. Co nieco przesuwasz w prawo, w rzeczywistości dzieli liczbę 2.

Dlatego (length >> 3) jest length/8 (w zaokrągleniu w dół), a (length >> 6) jest length/64.

Take (length/8)+(length/64) około length*(1/8+1/64) = length*0.140625 (w przybliżeniu)

1/7 = 0.142857...

+1 na końcu mogą być podzielone na +0.5 w każdym okresie, tak że length/8 zaokrągla się najbliżej (a nie w dół), i length/64 jest również zaokrąglana do najbliższej.

---

Ogólnie, można łatwo przybliżona 1/y, gdzie y = 2^n+-1 z podobnym zbliżenia bit-shift.

nieskończony geometryczny seria:

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

pomnożeniu przez x:

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

i zastępując 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) 

Podobny jest y = 2^n - 1.

Aby uzyskać przybliżoną wartość y = 2^n + 1, należy zastąpić 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) 

Następnie wystarczy obciąć serię nieskończoną do żądanej dokładności.

Answer 2

Mówiąc matematycznego tło do odpowiedzi ronalchn to:

od 7 = 8-1 = 8 * (1-1/8), przez podział cykl geometryczny o 7 jest taka sama jak mnożenie przez

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

---

Aby zrobić to samo dla podziału przez 5, można użyć tego 3 · 5 = 16-1, a więc

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

które zaprosić formułą

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

Answer 3

Zestaw x = 1/8 w The znany równości

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

i uprościć, aby dać

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

Pomnóż obie strony to by length w przykładzie, aby dać

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

pamiętać, że jest "dokładny" podział, a nie całkowitych Division - Piszę matematyki, a nie kod Java.

Następnie przybliżenie zakłada, że ​​trzecie i kolejne warunki będą zbyt małe, aby mieć znaczenie, i że średnio jeden z length/8 i length/64 prawdopodobnie będzie potrzebował zaokrąglać, a nie zaokrąglać w dół. Więc teraz, używając podziału całkowitego, length/7 = length/8 + length/64 + 1 jest bardzo dobrym przybliżeniem.

Wyrażenie, które podałeś przy użyciu operatorów bitowych, jest po prostu alternatywnym sposobem zapisu, pod warunkiem, że length jest dodatnie.

Answer 4

obliczeniowe wszystkie wartości

n/8 + n/64 - n/7 

błąd rośnie liniowo, podczas pobytu negatywne.

Poniższa lista przedstawia po raz pierwszy pojawia się dany błąd

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

Stosunek oczywiście tendencję do 1/448 = 1/8 + 1/64 - 1/7.