Целочисленное деление на 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. Поэтому вполне логично, что при делении на 7 мы получим повторяющуюся закономерность в основе 8.

Так при чем тут наш номер?

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

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