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

Тема в разделе "WASM.A&O", создана пользователем Mikl___, 16 янв 2009.

  1. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.708
    Как сделать сверхбыстрое деление? Может быть кто-нибудь сравнит с div или с подбором и последующей заменой деления на умножение, пока вот такой набросок
    Код (Text):
    1. mov edx,ДЕЛИМОЕ
    2.     bsr ecx,edx
    3.         mov ebx,ДЕЛИТЕЛЬ
    4.         bsr eax,ebx
    5.     sub ecx,eax
    6.     mov ebp,1
    7.     shl ebp,cl
    8.     shl ebx,cl
    9.     xor eax,eax; в EAX место под частное, в EDX -- остаток
    10.     or esi,-1
    11. a1: mov edi,ebx
    12.     add edi,esi
    13.     xor edi,esi; neg edi
    14.     add edx,edi
    15.              sbb esi,esi; esi=-1 or esi=0
    16.     mov edi,esi
    17.     and edi,ebp; edi=ebp or edi=0
    18.     add eax,edi
    19.     test edx,edx
    20.     jz a2;exit
    21.     shr ebx,1
    22.     shr ebp,1
    23.     jnz a1
    24. a2:
     
  2. Proteus

    Proteus Member

    Публикаций:
    0
    Регистрация:
    19 июн 2004
    Сообщения:
    344
    Адрес:
    Russia
    Что-то мне кажется вряд ли процедура, в которой два три десятка строк и два уловных перехода, сможет обогнать одну команду....

    Да вот ещё строки в ней непонятные есть...
    Код (Text):
    1. or esi,-1
     
  3. SII

    SII Воин против дзена

    Публикаций:
    0
    Регистрация:
    31 окт 2007
    Сообщения:
    1.483
    Адрес:
    Подмосковье
    Если делитель -- произвольное число, то обогнать команду DIV/IDIV невозможно. Вот если делителем является заранее известная величина, т.е. константа, тогда это вполне возможно, чем и пользуются "умные" компиляторы.
     
  4. meduza

    meduza New Member

    Публикаций:
    0
    Регистрация:
    15 авг 2008
    Сообщения:
    212
    В Уоррене есть глава, посвещенная делению произвольных целых чисел, а также отдельная глава выделена быстрым способам деления на константы.
     
  5. exst

    exst New Member

    Публикаций:
    0
    Регистрация:
    11 янв 2009
    Сообщения:
    91
    Прошу ссылочку.
     
  6. TermoSINteZ

    TermoSINteZ Синоби даоса Команда форума

    Публикаций:
    2
    Регистрация:
    11 июн 2004
    Сообщения:
    3.546
    Адрес:
    Russia
    Надеюсь, не сочтут варезом..
    http://rapidshare.com/files/185136839/Henry_warren-algorithmicheskie_tryuki_dla_programmistov.rar.html
     
  7. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.708
    Proteus
    or esi,-1 (3 байта) более компактный аналог mov esi,0FFFFFFFFh (5 байт)
    у Уоррена процедура деления длинее 23 строк -- однако его никто не ругает
     
  8. Proteus

    Proteus Member

    Публикаций:
    0
    Регистрация:
    19 июн 2004
    Сообщения:
    344
    Адрес:
    Russia
    Уорен чаще для RISK проц. пишет. И процедура соотв. имеет смысл на камне у которого команды деления нет. Там она видать и покороче будет. Вообще Уорена я первый раз читал, вроде всё понятно всё просто. Потом спустя год перечитываешь (когда что-то срочно вспомнить надо), и всё таки снова поражаешься, насколько красивые вещи в нём найти можно.

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

    persicum New Member

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

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

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.708
    persicum
    Если на скорую руку. Делим на заранее известные числа F3000001 или D0000001 оба числа 32 разрядные
    ищем обратное к ним (2^63)/F3000001=2262369603,9224372979735059262368 после запятой число больше 0,5 поправка не нужна
    (2^63)/D0000001=2643056796,7810650889744365762706 после запятой число больше 0,5 поправка не нужна.
    делимое = частное * делитель + остаток
    остаток = делимое - частное * делитель
    ищем остаток от деления на F3000001
    Код (Text):
    1. mov eax,2262369604; магическое число для F3000001
    2. mul X; X - число от которого берем остаток, в EDX получим частное от деления
    3. mov eax,0F3000001h
    4. shr edx,31
    5. mul edx
    6. neg eax
    7. add eax,X; в eax остаток от деления
    для D0000001 аналогично, только магическое число равно 2643056797
     
  11. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Спасибо за быструю реакцию! Однако есть пару возражений
    1) метод универсальный и не учитывает квази ферматную структуру чисел. Может, можно было бы подвигать регистры?

    2)...
     
  12. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    2) нельзя ли для тупеньких причесать код чтобы входные 64 бита лежали в паре регистров edx, eax. У Вас по ходу дела в X кладется старшая половина от учетверенного слова? А где младшая? Или это я торможу, или Вы перепутали 64 битные данные с 32-х битными?
     
  13. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.708
    С этого места можно по-подробнее? :)
    ЗЫ. Я же написал "на скорую руку" дома поупражняюсь, до завтра терпимо?
     
  14. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Если число больше D0000001h, то остаток равен x-D0000001h. Иначе остаток равен x. Это верно для 32-битных чисел без знака.
    Код (Text):
    1. sub eax,D0000001h
    2. sbb edx,edx
    3. and edx,D0000001h
    4. add eax,D0000001h
    Жесть!
     
  15. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Многоуважаемый 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
     
  16. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Чё-то сообщение не редактируется. Я хотел написать
    Код (Text):
    1. sub eax,D0000001h
    2. sbb edx,edx
    3. and edx,D0000001h
    4. add eax,edx
     
  17. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Если точнее, это числа Proth'а, которые я выловил с помощью одноименной программы, они же делители чисел Ферма 2^2^n+1.
     
  18. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    А я хочу редуцировать 64-битные числа по модулю F3000001. Переполнения гарантированно нет, т.к. они сами получаются в результате MUL и лежат в паре регистров EAX-EDX.
     
  19. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    за sbb edx,edx спасибо, я использовал в некоторых случаях sar edx,31 но sbb круче трюк!
     
  20. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Ещё так можно
    Код (Text):
    1. mov   edx,eax
    2. sub   eax,D0000001h
    3. cmovc eax,edx
    Про замену деления умножением есть в AMD Athlon™ Processor x86 Code Optimization Guide.