Целочисленное деление на 7 - программирование

Отправьте мой ответ в:

Является ли это выражение правильным в препроцессоре C

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

Как упоминалось в ответе, 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

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

Ответ 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 (huh? Нигде близко к 8 в этот момент.)

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

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

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

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