Выполнение целочисленного деления с использованием умножения

Question

Глядя на сборку x86, созданную компилятором, я заметил, что (беззнаковые) целые деления иногда реализуются как целочисленные умножения. Эти оптимизации, кажется, следует форме

value/n => (value * ((0xFFFFFFFF/n) + 1))/0x100000000 

Например, выполняя деление на 9:

12345678/9 = (12345678 * 0x1C71C71D)/0x100000000 

Деление на 3 будет использовать умножение 0x55555555 + 1, и так далее.

Используя тот факт, что инструкция mul хранит большую часть результата в регистре edx, конечный результат деления можно получить, используя одно умножение с магическим значением. (Хотя эта оптимизация иногда используется в сочетании с побитным сдвигом в конце.)

Мне хотелось бы получить некоторое представление о том, как это работает. Когда этот подход действителен? Почему нужно добавить к нашему «магическому числу»?

Answer 1

Этот метод называется «разделение инвариантным умножением».

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

Таким образом, вместо вычисления:

N/D = Q 

вы сделать что-то вроде этого, вместо:

N * (1/D) = Q 

где 1/D является возвратным, который может быть предвычисленными.

В принципе, обратные значения являются неточными, если D - это сила двух. Таким образом, будет какая-то ошибка округления. +1, который вы видите, предназначен для исправления ошибки округления.

---

Наиболее распространенным примером является деление на 3:

N/3 = (N * 0xaaaaaaab) >> 33 

Где 0xaaaaaaab = 2^33/3 + 1.

Этот подход будет обобщен на другие делители.