2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Замена целочисленного деления на умножение и сдвиг (теория)
Сообщение25.12.2015, 09:22 
Предлагаю обсудить следующую видео-лекцию, касающуюся замены целочисленного деления на умножение и сдвиг.

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

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

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

 
 
 
 Re: Замена целочисленного деления на умножение и сдвиг (теория)
Сообщение25.12.2015, 09:51 
А для чего эта замена нужна или может понадобиться?

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

 
 
 
 Re: Замена целочисленного деления на умножение и сдвиг (теория)
Сообщение25.12.2015, 10:44 
Можно добавить ссылки на "Алгоритмические трюки для программистов" Уоррена мл. Там рассматривается эта задача.

 
 
 
 Re: Замена целочисленного деления на умножение и сдвиг (теория)
Сообщение25.12.2015, 11:26 
Цитата:
А для чего эта замена нужна или может понадобиться?

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

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

 
 
 
 Re: Замена целочисленного деления на умножение и сдвиг (теория)
Сообщение25.12.2015, 17:19 
mihailm в сообщении #1085681 писал(а):
А для чего эта замена нужна или может понадобиться?
Добавлю, на некоторых процессорах (многие микроконтроллеры) команда умножения есть, а команды деления нет.

buti в сообщении #1085709 писал(а):
На некоторых процессорах (Intel и AMD точно из их числа) такая замена может сильно ускорить деление.
Да, а ещё тогда можно будет воспользоваться MMX/SSE/AVX расширениями и ещё более ускорить программу.

 
 
 
 Re: Замена целочисленного деления на умножение и сдвиг (теория)
Сообщение25.12.2015, 20:50 
Аватара пользователя
buti
Ну что же. Четыре с минусом.

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

 
 
 
 Re: Замена целочисленного деления на умножение и сдвиг (теория)
Сообщение30.12.2015, 05:55 
Аватара пользователя
Dmitriy40 в сообщении #1085777 писал(а):
Добавлю, на некоторых процессорах (многие микроконтроллеры) команда умножения есть, а команды деления нет.

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

 
 
 
 Re: Замена целочисленного деления на умножение и сдвиг (теория)
Сообщение30.12.2015, 09:20 
Да и в программах, скомпиленных под x86, я встречал подобную фишку. Компилятору виднее. =)

 
 
 
 Re: Замена целочисленного деления на умножение и сдвиг (теория)
Сообщение07.01.2016, 05:09 
Аватара пользователя
12d3 в сообщении #1086958 писал(а):
Компилятору виднее. =)

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

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group