Замена целочисленного деления на умножение и сдвиг (теория)

[buti]

Предлагаю обсудить следующую видео-лекцию, касающуюся замены целочисленного деления на умножение и сдвиг.

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

- Ссылка на архив с презентацией и программой для подбора параметров:
https://yadi.sk/d/5PLnPY0KmTaXz

Какие ещё моменты стоило упомянуть в лекции? С чем вы согласны или не согласны? Полезна ли была лекция?

[mihailm]

А для чего эта замена нужна или может понадобиться?

[arseniiv]

Делить на константу бывает дольше, чем проделать те манипуляции. В былые времена так нередко преобразовывали при оптимизации. Сейчас, кажется, распространённые компиляторы C/C++ (и чего-нибудь ещё) делают такое преобразование, если в нём есть смысл, автоматически; точно не скажу.

[slavav]

Можно добавить ссылки на "Алгоритмические трюки для программистов" Уоррена мл. Там рассматривается эта задача.

[buti]

Цитата:

А для чего эта замена нужна или может понадобиться?

На некоторых процессорах (Intel и AMD точно из их числа) такая замена может сильно ускорить деление.

На процессорах, которые не поддерживают умножение с расширением результата до 64 бит это вряд ли даст выигрыш, но тут надо проверять, а практики ещё не было.

[Dmitriy40]

mihailm в сообщении #1085681 писал(а):

А для чего эта замена нужна или может понадобиться?

Добавлю, на некоторых процессорах (многие микроконтроллеры) команда умножения есть, а команды деления нет.

buti в сообщении #1085709 писал(а):

На некоторых процессорах (Intel и AMD точно из их числа) такая замена может сильно ускорить деление.

Да, а ещё тогда можно будет воспользоваться MMX/SSE/AVX расширениями и ещё более ускорить программу.

[Pavia]

buti
Ну что же. Четыре с минусом.

Лекцию всю переписать. Теорию можете взять отсюда
http://www.agner.org/optimize/optimizing_assembly.pdf
Во-вторых когда пишете статью в конце надо приводить источники информации.

[bondkim137]

Dmitriy40 в сообщении #1085777 писал(а):

Добавлю, на некоторых процессорах (многие микроконтроллеры) команда умножения есть, а команды деления нет.

ARM-ы все старые (аля ARMv4) не умеют делить. и практически все компиляторы при делении на константу прибегают к такому трюку. программисты раньше также прибегали, когда делить приходилось на условную константу

[12d3]

Да и в программах, скомпиленных под x86, я встречал подобную фишку. Компилятору виднее. =)

[bondkim137]

12d3 в сообщении #1086958 писал(а):

Компилятору виднее. =)

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