How does this approximation of division using bit shift operations work?

Question

The following line of code appears in java.util.DualPivotQuicksort :

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

The variable length is int greater than or equal to 47.

I know how a signed shift operator works. But I do not know why these specific operations lead to the approximation of division by 7. Can someone explain, please?

Answer 1

>> is a bit shift. Each bit is shifted to the right, essentially divides the number 2.

Therefore, (length >> 3) length/8 (rounded), and (length >> 6) - length/64 .

Take (length/8)+(length/64) about length*(1/8+1/64) length*0.140625 length*(1/8+1/64) = length*0.140625 (approximately)

1/7 = 0.142857...

+1 at the end can be divided by +0.5 for each member, so length/8 rounded to the nearest (instead of down), and length/64 also rounded to the nearest.

---

In general, you can easily approximate 1/y , where y = 2^n+-1 with a similar bit shift approximation.

Infinite geometric series:

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

Multiplication by x:

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

And substituting 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) 

This approaches y = 2^n - 1 .

To get closer to y = 2^n + 1 , replace 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) 

Then simply crop the endless row to the desired precision.

Answer 2

Set x = 1/8 to the known equality

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

and simplify to give

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

Multiply both sides of this by length in your example to give

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

Note that this is an “exact” division, not an integer division. I am writing math, not Java code.

Then in the approximation it is assumed that the third and subsequent terms will be too small for matter and that, on average, one of length / 8 and length / 64 most likely needs to be rounded rather than rounded. So now, using integer division, length / 7 = length / 8 + length / 64 + 1 is a very good approximation.

The expression you gave using bitwise operators is just an alternative way to write if length positive.

Answer 3

To set the math background for ronalchn's answer:

Since 7 = 8-1 = 8 * (1-1 / 8), the division of the geometric series by 7 coincides with the multiplication by

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

---

To do the same for dividing by 5, one could use this 3 · 5 = 16-1 and therefore

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

which would invite a formula like

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

Answer 4

Calculation of all values

 n/8 + n/64 - n/7 

the error grows linearly, remaining negative.

The list below shows the first time this error appears.

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

The ratio obviously tends to 1/448 = 1/8 + 1/64 - 1/7 .