Целочисленное деление на 7

Question

Источник мой ответ на:

Is this expression correct in C preprocessor

Я немного из моего форте здесь, и я пытаюсь понять, как это конкретные оптимизации работы.

Как уже говорилось в ответе, GCC оптимизирует целочисленное деление на 7:

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

Что переводится обратно в C, как:

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

Давайте посмотрим на первую часть:

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

Почему этот номер?

Ну, давайте возьмем 2^64 и разделим его на 7 и посмотрим, что всплывает.

2^64/7 = 2635249153387078802.28571428571428571429 

Это похоже на беспорядок, что, если мы преобразуем его в восьмеричное?

0222222222222222222222.22222222222222222222222 

Это очень симпатичный повторяющийся шаблон, безусловно, не может быть совпадением. Я имею в виду, что 7 - это 0b111, и мы знаем, что когда мы делим на 99, мы склонны получать повторяющиеся шаблоны в базе 10. Таким образом, имеет смысл, что мы получим повторяющийся шаблон в базе 8, когда разделим на 7.

Итак, где наш номер входит?

(int32_t)-1840700269 такая же, как (uint_32t)2454267027

* 7 = 17179869189

И, наконец, 17179869184 является 2^34

Это означает, что 17179869189 является самым близким кратным 7 2^34. Или, это еще один способ 2454267027 наибольшее число, которое помещается в uint32_t, которое при умножении на 7 очень близка к мощности 2

Что это число в восьмеричной системе?

0222222222223 

Почему это важно? Ну, мы хотим разделить на 7. Это число составляет 2^34/7 ... приблизительно. Поэтому, если мы умножим его, а затем сдвинем влево 34 раз, мы должны получить число, очень близкое к точному числу.

Последние две строки выглядят так, как будто они предназначены для исправления ошибок аппроксимации.

Возможно, кто-то, у кого есть немного больше знаний и/или опыта в этой области, может прослушивать это.

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

Неудачи начинаются в 3435973841, который, как ни странно 0b11001100110011001100110011010001

Классифицируя почему приближение не удается немного за меня, и почему патчи исправить это как хорошо.Кто-нибудь знает, как волшебство работает дальше того, что я здесь положил?

Answer 1

Первая часть алгоритма умножается на приближение к обратному значению 7. В этом случае мы приближаемся к вычислению обратной величины с умножением целого числа и правым сдвигом бит.

Во-первых, мы видим значение -1840700269 (восьмеричное -015555555555) как 32-битное целое число. Если вы читаете это как 32-битное целое число без знака, оно имеет значение 2454267027 (октал 22222222223). Оказывается, что 2454267027/2^34 - очень близкое целочисленное приближение к 1/7.

Почему мы выбираем это число и эту силу 2? Чем больше мы используем целые числа, тем ближе приближение. В этом случае 2454267027 представляется наибольшим целым числом (удовлетворяющим указанному выше свойству), с помощью которого вы можете размножать подписанный 32-битный int без переполнения 64-битного int.

Далее, если мы сразу сдвинем с >> 34 и сохраним результат в 32-битном int, мы потеряем точность в двух младших битах. Эти биты необходимы для определения правильного пола для целочисленного деления.

Я не уверен, что вторая строка была правильно переведена из кода x86. В этот момент temp составляет приблизительно num * 4/7, поэтому num * 4/7 + num к этому и бит-сдвигу будет дать вам приблизительно num * 1/7 + num * 1/4, что довольно большая ошибка.

Например, возьмите на вход 57, где 57 // 7 = 8. Я проверил ниже в коде, а также:

• 57 * 2454267027 = 139893220539
• 139893220539 >> 32 = 32 (около 57 * 4/7 = 32.5714... в этой точке)
• 32 + 57 = 89
• 89 >> 2 = 22
(да ?? Nowhere близко к 8 в этой точке.)

В любом случае, для последней строки это корректировка, которую мы делаем после вычисления знакового целочисленного деления таким образом. Цитирую из раздела от восторга Хакера на знаковом делении:

код наиболее естественно вычисляет результат пола деления, так что нам нужно коррекции, чтобы сделать его вычислить обычный усечен в стороне 0 результата. Это можно сделать с помощью трех вычислительных инструкций: , добавляя к дивиденду, если дивиденд отрицательный.

В этом случае (со ссылкой на ваш другой пост), кажется, что вы делаете подписанный сдвиг, поэтому он будет вычитать -1 в случае отрицательного числа; давая результат +1.

Это еще не все, что вы можете сделать; вот еще сумасшедший blog post about how to divide by 7 with just a single multiplication.