Алгоритм деления без восстановления

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

Да вот ещё строки в ней непонятные есть...

Код (Text):

1. or esi,-1

 

Если делитель -- произвольное число, то обогнать команду DIV/IDIV невозможно. Вот если делителем является заранее известная величина, т.е. константа, тогда это вполне возможно, чем и пользуются "умные" компиляторы.

 

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

 

Прошу ссылочку.

 

Уорен чаще для RISK проц. пишет. И процедура соотв. имеет смысл на камне у которого команды деления нет. Там она видать и покороче будет. Вообще Уорена я первый раз читал, вроде всё понятно всё просто. Потом спустя год перечитываешь (когда что-то срочно вспомнить надо), и всё таки снова поражаешься, насколько красивые вещи в нём найти можно.

А так делилка неплохая получилась...

 

Mikl___, выручай!
Собсна, нужно брать остаток быстро от деления на F3000001 или D0000001, можно выбрать где проще... Такие заковыристые модули нужны для Быстрого Преобразования Фурье на 2^n точках. Сама процедура уже написана, но там стоит заглушка в виде DIV =))) Пробовал еще Фурье на числе 65537, там взятие модуля занимает строчек десять, но они работают в разы быстрее DIV. A сначала я сам тоже весьма скептически относился к замене одной DIV на кучу кода. Но это было квази 16-битное Фурье, а хочется квази 32-х битное. Для взятия этих остатков без деления нужно всетаки как- то ухитряться делить на F3 или 0D... С таблицами связываться не хочется, хочется чтобы все в регистрах было

Короче говоря, нужно 64-битное число в регистрах edx,eax редуцировать по модулю F3000001 и вернуть резалт в регистре eax. Можно использовать сдвиги регистровых пар типа shrd eax,edx,24 , а на счет mul точно не знаю, можно обойтись без него или нет.

 

Спасибо за быструю реакцию! Однако есть пару возражений
1) метод универсальный и не учитывает квази ферматную структуру чисел. Может, можно было бы подвигать регистры?

2)...

 

2) нельзя ли для тупеньких причесать код чтобы входные 64 бита лежали в паре регистров edx, eax. У Вас по ходу дела в X кладется старшая половина от учетверенного слова? А где младшая? Или это я торможу, или Вы перепутали 64 битные данные с 32-х битными?

 

Если число больше D0000001h, то остаток равен x-D0000001h. Иначе остаток равен x. Это верно для 32-битных чисел без знака.

Код (Text):

1. sub eax,D0000001h
2. sbb edx,edx
3. and edx,D0000001h
4. add eax,D0000001h

Жесть!

 

Многоуважаемый Mikl___! Если Вы всерьез решили помочь с написанием оптимального кода, то можете возвращаться к этой проблеме хоть всю неделю, хоть две, ибо оно конечно терпит, поскольку стандартный DIV вставлен пока в качестве вполне работоспособной заглушки.

x = a*2^24 + b = (q*F3+r)*2^24 + b + q - q = q*(F3*2^24+1) + r*2^24 + b - q = r*2^24 + b - q

 

Чё-то сообщение не редактируется. Я хотел написать

Код (Text):

1. sub eax,D0000001h
2. sbb edx,edx
3. and edx,D0000001h
4. add eax,edx

 

Если точнее, это числа Proth'а, которые я выловил с помощью одноименной программы, они же делители чисел Ферма 2^2^n+1.

 

А я хочу редуцировать 64-битные числа по модулю F3000001. Переполнения гарантированно нет, т.к. они сами получаются в результате MUL и лежат в паре регистров EAX-EDX.

 

за sbb edx,edx спасибо, я использовал в некоторых случаях sar edx,31 но sbb круче трюк!

 

Ещё так можно

Код (Text):

1. mov   edx,eax
2. sub   eax,D0000001h
3. cmovc eax,edx

Про замену деления умножением есть в AMD Athlon™ Processor x86 Code Optimization Guide.