Как работает эта аппроксимация деления с использованием операций сдвига бит?

Question

В java.util.DualPivotQuicksort, следующая строка кода появляется:

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

Переменная length является int больше или равно 47.

Я знаком с тем, как работает подписанный оператор правого сдвига. Но я не знаю, почему эти конкретные операции приводят к приближению деления на 7. Может ли кто-нибудь объяснить, пожалуйста?

Answer 1

>> is bithift. Каждый бит вы сдвиг вправо, фактически делит число 2.

Поэтому (length >> 3) является length/8 (округление вниз), и (length >> 6) является length/64.

Возьмите (length/8)+(length/64) приблизительно length*(1/8+1/64) = length*0.140625 (приблизительно)

1/7 = 0.142857...

+1 в конце может быть разделен на +0.5 для каждого термина, так что length/8 округляется до ближайшего (а не вниз), и length/64 также округляется до ближайшего.

---

В общем, вы можете легко приблизительная 1/y, где y = 2^n+-1 с аналогичным приближению бит сдвига.

Бесконечная геометрическая прогрессия является:

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

Умножив х:

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

И подставляя 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) 

Это приближает y = 2^n - 1.

Чтобы приблизиться, y = 2^n + 1, вместо этого заменить 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) 

Затем просто обрезайте бесконечную серию с требуемой точностью.

Answer 2

Наносить математический фон для ответа ronalchn в:

С 7 = 8-1 = 8 * (1-1/8), по геометрической серии деление на 7 таком же, как умножение на

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

---

Чтобы сделать то же самое для деления на 5, следует использовать это 3 · 5 = 16-1 и, следовательно,

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

, который бы предложить формулу, как

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

Answer 3

Установите x = 1/8 в хорошо известное равенство

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

и упростить, чтобы дать

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

Умножить обе стороны этого по length в вашем примере, чтобы дать

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

Обратите внимание, что это «точное» деление, а не целое подразделение - Я пишу математику, а не Java код.

Тогда в приближении предполагается, что третий и последующие термины будут слишком малы для материи и что в среднем один из length/8 и length/64, скорее всего, нуждается в округлении, а не округлении вниз. Итак, теперь, используя целочисленное деление, length/7 = length/8 + length/64 + 1 - очень хорошее приближение.

Выражение, которое вы указали, используя побитовые операторы, является просто альтернативным способом его написания, если length положителен.

Answer 4

Вычислительный все значения

n/8 + n/64 - n/7 

ошибка растет линейно, оставаясь отрицательным.

В списке ниже показан первый раз, данная ошибка появляется

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

отношение, очевидно, имеет тенденцию к 1/448 = 1/8 + 1/64 - 1/7.