Всем привет.
Нашел у себя на диске утилиту для вычисления формул и алгоритмов быстрого умножения и деления на константу.
Выкладываю здесь, вдруг кому сгодится. У меня есть еще и версия для 64-битных констант, но она еще тормознее.
Умножение реализовывается с помощью сложений/вычитаний, сдвигов. Деление и остаток с помощью умножения.
Для поиска оптимальной формулы умножения использованы флгоритмы: Горнера, взвешивание дерева, взвешивание обратного дерева, факторизация с группировкой. Для вычисления констант деления использован алгоритм Гранлунда-Монтгомери.
В будущем может добавлю еще алгоритмов для поиска оптимума, реализую скоростное взятие остатка и т.д...
Расписывать умножение на ассемблере мне было лень, надеюсь все знают, как складывать и сдвигать ;-)
Программа не оптимальна и тормозит на больших константах, и вообще не понимает отрицательных.
Если программа выводит страшную строку типа "result = (L = (M = (L+0x2*(L+0x20*(L))); N = (0x4000*M+0x1000*M+0x100*M+0x80*M-0x8*M+0x1*M)); M = (L+0x800*(L))" это расшифровывается по правилам С.
Т.е. последовательность шагов будет такая: L = исходное число; M = (L+0x2*(L+0x20*(L))); N = (0x4000*M+0x1000*M+0x100*M+0x80*M-0x8*M+0x1*M)); L = N; M = (L+0x800*(L)); result = M; вот и все...
Все баги, пожелания, ругань и пр. дублируйте по возможности в почту.


_96987228__constant.exe

Умножение занимает 2-4 такта(уж побыстрее чем цикл сложения), деление выполняется через умножение, как рассчитывать на что умножать написано в книге Агнера Фога про оптимизацию. Зачем же тогда всё это надо?

dragon
Умножение занимает 2-9

Quantum
В той же книжке Фога написано до 4 тактов, это наверное на PIV 2-9

А. Фог пишет, что максимум 11 тактов, но для старых Pentium'ов, а для более новых образцов - до 9 тактов. Об этом также пишет Касперский в статье про мат. операции.

Не забывайте что есть другие процессоры нежели x86. Собственно под них изначально и писалась программа (как идея), а потом была пересена. На "хилых" микроконтроллерах умножать с помощью сложений и сдвигов бывает эффективнее, не говоря уж о том что у некоторых моделей вообще нет команды умножения...

Об этом также пишет Касперский в статье про мат. операции.

Really? Евгений?? ;-)

26.5 Целочисленное умножение (все процессоры)

Целочисленное умножение занимает до 9 тактов на PPlain и PMMX и до 4 тактов на PPro, PII и PIII. Поэтому часто выгоднее бывает заменить умножение на константу и комбинацию других инструкций, таких как SHL, ADD, SUB и LEA.

Нафига по первым пням ориентироваться. Про PIV и атлоны у него не написано, но вряд ли умножение будет длиться дольше чем на третьем пне.

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

Asterix
Наверное Крис Касперски, хотя тот тоже насмотрелся на оптимизированный код в вирях и решил написать, как они "мат. операции" производят :)

dragon
Нафига по первым пням ориентироваться.
Если так поступают "оптимизирующие" компиляторы, то на то должен быть резон, разве не так? Рекомендую помедитировать над этим вопросом.

Asterix
dragon
Хватит издеваться над бедным человеком ;-)