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

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

  1. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Непонятно, что общего у этого кода с Montgomery. Монтгомери нужно полтора MUL для редукции, а здесь примерно то же что и у Майкла____. Еще нужен мультипликативный обратный с FFF00001, но приведенная константа на него не похожа.

    Так и не понятно, что делать при переполнении при сложении. Вычитать трансформированный p ?

    Вот код #27 как раз использует специфику чисел, близких к FFFFFFFF. С обычным простым от балды работать не будет. Классно работает у меня еще с FFFFFFFB, умножая на 5
     
  2. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    А монтгомери полной редукции не гарантирует, он тока гарантирует отсутствие потери информации при переполнении, что частичный остаток влезет в 32-бит. Так что тут тоже нужен гимор с доводкой числа.
     
  3. diamond

    diamond New Member

    Публикаций:
    0
    Регистрация:
    21 май 2004
    Сообщения:
    507
    Адрес:
    Russia
    Предпоследний вариант кода из #81, до избавления от mul, принцип работы в точности такой же:
    Код (Text):
    1. start:
    2.     mov ebp, 0xFFF00001
    3.     mov eax, 0x12345678
    4.     call    input2coded
    5.     mov ebx, eax
    6.     mov eax, 0x9ABCDEF0
    7.     call    input2coded
    8.     mov edx, ebx
    9.     call    coded_mul
    10.     call    coded2output
    11. ; eax = residue
    12.     ret
    13.  
    14. coded2output:
    15. ; eax -> eax
    16.     xor edx, edx
    17.     jmp coded_mul_doit
    18.  
    19. input2coded:
    20. ; eax -> eax
    21.     mov edx, 0x0FDFFF01
    22. coded_mul:
    23. ; eax*edx -> eax
    24.     mul edx
    25. coded_mul_doit:
    26.     imul    eax, 0x100001 ; = -0xFFEFFFFF
    27.     mov edi, edx
    28.     mul ebp
    29.     sub edi, edx
    30.     sbb eax, eax
    31.     and eax, ebp
    32.     add eax, edi
    33.     ret
    Мультипликативный обратный здесь равен 0xFFEFFFFF, он же -0x100001, что прекрасно описывается сдвигами.
    Этот код, как и предыдущий, а) полностью рабочий (можно проверять, заменяя 0x12345678 и 0x9ABCDEF0 на что-то своё) и б) следует методу Монтгомери.
    Тупой работающий вариант:
    Код (Text):
    1. coded_add:
    2. ; eax + edx -> eax
    3.     add eax, edx
    4.     jc  overflow
    5.     cmp eax, 0xFFF00001
    6.     jae overflow
    7.     ret
    8. overflow:
    9.     sub eax, 0xFFF00001
    10.     ret
    Тупость заключается в лишних ветвлениях, для большей скорости их нужно устранить.
     
  4. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Ну оптимальное сложение по модулю выглядит совсем по другому. Но вопрос не в этом. Я тоже сначала юзал заглушку на jc. Вопрос, если числа трансформированы, то как складывать? Чистый p выглядит подозрительным
     
  5. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    похвалялась репа что с медом хороша... FFFOOOOI и сам для сдвигов хорош...
     
  6. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    за Монтгомери конечно спасибо, будем изучать... Еще бы разобраться со сложением трансформированных величин... Но впечатления двойственные, поскоку модуль специального вида, очевидно что и без монтгомери все можно сделать
     
  7. diamond

    diamond New Member

    Публикаций:
    0
    Регистрация:
    21 май 2004
    Сообщения:
    507
    Адрес:
    Russia
    Точно так же, как если они не трансформированы. Нужно просто вычитать p, если результат (с учётом возможного 32-битного переполнения) оказался больше или равен p.
    Ага, код из #78 это использует (потому что в коде из #83 можно заметить команду mul ebp, а в ebp хранится p).
     
  8. bugaga

    bugaga New Member

    Публикаций:
    0
    Регистрация:
    1 июл 2007
    Сообщения:
    361
    хм.. столкнулся с мелкой проблемой относительно деления на пять.
    подсмотрев трюк у gcc..
    Код (Text):
    1. unsigned short int xz (unsigned int my)
    2. {
    3.   return my / 5;
    4. }
    5. .globl _xz
    6.     .def    _xz;    .scl    2;  .type   32; .endef
    7. _xz:
    8.     mov edx, -858993459
    9.     mul edx
    10.     shr edx, 2
    11.     mov eax, edx
    12.     ret
    скопипастил сие решение, но решил оптимизнуть под свой код. в процесе чего были навешаны некоторые баги, и в результате что то я не понял.. почему работает как надо??

    (а то код выполняется в критическом режиме...)
    Код (Text):
    1. program xz;  
    2. var
    3.     hook: function:integer;
    4.  
    5. procedure IDTHook; forward;
    6.  
    7. procedure _rise;
    8. asm  sub [esp], offset IdtHook+5;
    9.      mov eax, $CCCCCCCD // собственно тут
    10.      mul eax, [esp]           // деление
    11.      add esp,4
    12. end;
    13.  
    14. procedure IDTHook;
    15. begin // ряд из 5-ти байтовых CALL-ов
    16.     _rise(*00*); // Divide Error
    17.     _rise(*01*); // Debug Exception
    18.     _rise(*02*); // NMI Interrupt
    19.     _rise(*03*); // Breakpoint
    20.     _rise(*04*); // INTO-detected Overflow
    21.     _rise(*05*); // BOUND Range Exceeded
    22.     _rise(*06*); // Invalid Opcode
    23.     _rise(*07*); // Device Not Available
    24.     _rise(*08*); // Double Fault
    25. // и т.д
    26. end;
    27.  
    28. begin
    29.     hook :=  pointer(integer(@IdtHook)+$7 * 5);
    30.     writeln (hook() );
    31. end.
     
  9. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    http://www.wasm.ru/baixado.php?mode=tool&id=203
     
  10. bugaga

    bugaga New Member

    Публикаций:
    0
    Регистрация:
    1 июл 2007
    Сообщения:
    361
    murder сенькс, крутая прожка..

    вроде разобрался, в моем случае числа только кратные 5, и за чего оказалось возможным избавиться от xxx SHR 2 (пустячок, а приятно...)
     
  11. edemko

    edemko New Member

    Публикаций:
    0
    Регистрация:
    25 ноя 2009
    Сообщения:
    454
    капут :)
    Код (Text):
    1. ; ecx:ebx:eax <- 1/eax
    2. ; flags       <- ?
    3. ; rus: Почему так: www.code.google.com\p\fasmme\ -> 80 bit floats.
    4. ;      Внимательно прочитав инфу по ссылке выше, вы поймете, что весь трюк заключается в преобразовании числа 1 в двоичной системе счисления - в с основанием eax.
    5. ;      Если вы полны извращенства, "1/eax" - не лимит этой процедуры, т.к. вместо 1...
    6. ; enu: Theory: www.code.google.com\p\fasmme\ -> 80 bit floats
    7. ;      As you can see, the trick is based on binary 1 into eax'ary count system encoding.
    8. ;      "1/eax" can be replaced with "2/eax" etc.
    9.  
    10.         ;format pe gui 4.0
    11.         ;include 'win32ax.inc'
    12.         ;
    13.         ;section '' code executable import readable writable
    14.         ;  library kernel32,'kernel32.dll',\
    15.         ;          user32,'user32.dll'
    16.         ;
    17.         ;  include 'api\kernel32.inc'
    18.         ;  include 'api\user32.inc'
    19.         ;
    20.         ;  buf0 db 'dec: 0.'
    21.         ;  buf1 rb 32;*3 * log(10;2)
    22.         ;       db 10,'bin: 0.'
    23.         ;  buf2 rb 32*3
    24.         ;       db 10,'hex: 0.'
    25.         ;  buf3 rb 32*3/4
    26.         ;       db 0
    27.         ;
    28.         ;  entry $
    29.         ;        mov     eax,10;$ffff'ffff
    30.         ;        call    reciprocal_dword
    31.         ;        ;dec
    32.         ;        push    ecx ebx eax  ecx ebx eax  ecx ebx eax
    33.         ;        mov     ecx,32
    34.         ;        mov     edi,buf1
    35.         ;     @@:mov     eax,10
    36.         ;        mul     dword[esp+8]
    37.         ;        mov     [esp+8],eax
    38.         ;        lea     ebx,[edx+'0']
    39.         ;        mov     eax,10
    40.         ;        mul     dword[esp+4]
    41.         ;        mov     [esp+4],eax
    42.         ;        add     [esp+8],edx
    43.         ;        adc     ebx,0
    44.         ;        mov     eax,10
    45.         ;        mul     dword[esp]
    46.         ;        add     [esp+4],edx
    47.         ;        adc     dword[esp+8],0
    48.         ;        adc     ebx,0
    49.         ;        mov     al,bl
    50.         ;        stosb
    51.         ;        loop    @b
    52.         ;        add     esp,12
    53.         ;        ;bin
    54.         ;        mov     ecx,32*3
    55.         ;        mov     edi,buf2
    56.         ;        pop     ebx edx esi
    57.         ;     @@:shl     ebx,1
    58.         ;        rcl     edx,1
    59.         ;        rcl     esi,1
    60.         ;        mov     al,0
    61.         ;        adc     al,'0'
    62.         ;        stosb
    63.         ;        loop    @b
    64.         ;        ;hex
    65.         ;        mov     ecx,32*3/4
    66.         ;        mov     edi,buf3
    67.         ;        pop     ebx edx esi
    68.         ;     @@:shld    eax,esi,4
    69.         ;        shld    esi,edx,4
    70.         ;        shld    edx,ebx,4
    71.         ;        shl     ebx,4
    72.         ;         and     al,$0f
    73.         ;         add     al,'0'
    74.         ;         daa
    75.         ;         cmp     al,$0a+'0'+$06
    76.         ;         sbb     al,-1
    77.         ;        stosb
    78.         ;        loop     @b
    79.         ;        ;
    80.         ;        invoke  MessageBoxA,0,buf0,'reciprocal_dword',0
    81.         ;
    82.         ;        invoke  ExitProcess,0
    83.  
    84. proc reciprocal_dword
    85.         xor     ebx,ebx
    86.         push    ebx ebx ebx
    87.         lea     ecx,[ebx+32*3]
    88.         inc     ebx
    89. .to_bin:shl     ebx,1
    90.         jc      .put_
    91.         cmp     eax,ebx
    92.         ja      .put
    93.   .put_:sub     ebx,eax
    94.         stc
    95.   .put: rcl     dword[esp],1
    96.         rcl     dword[esp+4],1
    97.         rcl     dword[esp+8],1
    98.         loop    .to_bin
    99.         pop     eax ebx ecx
    100.         ret     0             ; 2010_11_28
    101. endp
     
  12. edemko

    edemko New Member

    Публикаций:
    0
    Регистрация:
    25 ноя 2009
    Сообщения:
    454
    Код (Text):
    1. ; edx:ecx:ebx:eax <- 1/ebx:eax
    2. ; flags           <- ?
    3.  
    4.          ;format pe gui 4.0
    5.          ;include 'win32ax.inc'
    6.          ;
    7.          ;section '' code executable import readable writable
    8.          ;  library kernel32,'kernel32.dll',\
    9.          ;          user32,'user32.dll'
    10.          ;
    11.          ;  include 'api\kernel32.inc'
    12.          ;  include 'api\user32.inc'
    13.          ;
    14.          ;  buf0 db 'bin: '
    15.          ;  buf1 rb 32*4
    16.          ;       db 0
    17.          ;
    18.          ;  entry $
    19.          ;        mov     ebx,0;$ffff'ffff
    20.          ;        mov     eax,3;$ffff'ffff
    21.          ;        call    reciprocal_qword
    22.          ;        ;bin
    23.          ;        push    edx ecx ebx eax
    24.          ;        mov     ecx,32*4
    25.          ;        mov     edi,buf1
    26.          ;     @@:shl     dword[esp],1
    27.          ;        rcl     dword[esp+4],1
    28.          ;        rcl     dword[esp+8],1
    29.          ;        rcl     dword[esp+12],1
    30.          ;        mov     al,0
    31.          ;        adc     al,'0'
    32.          ;        stosb
    33.          ;        loop    @b
    34.          ;        add     esp,12
    35.          ;        ;
    36.          ;        invoke  MessageBoxA,0,buf0,'reciprocal_qword',0
    37.          ;
    38.          ;
    39.          ;        invoke  ExitProcess,0
    40.  
    41. proc reciprocal_qword
    42.         push    edi
    43.         xor     edi,edi
    44.         push    edi edi edi edi
    45.         lea     edx,[edi+1]
    46.         lea     ecx,[edx+32*4-1]   ; < lea ecx,[edi+32*4]
    47.  
    48. .to_bin:shl     edx,1
    49.         rcl     edi,1
    50.         jc      .put_
    51.         cmp     ebx,edi
    52.         jb      .put_
    53.         ja      .put
    54.         cmp     eax,edx
    55.         ja      .put
    56.   .put_:sub     edx,eax
    57.         sbb     edi,ebx
    58.         stc
    59.   .put: rcl     dword[esp],1
    60.         rcl     dword[esp+4],1
    61.         rcl     dword[esp+8],1
    62.         rcl     dword[esp+12],1
    63.         loop    .to_bin
    64.  
    65.         pop     eax ebx ecx edx
    66.         pop     edi
    67.         ret     0                  ; 2010_11_28
    68. endp
     
  13. edemko

    edemko New Member

    Публикаций:
    0
    Регистрация:
    25 ноя 2009
    Сообщения:
    454
    Воплотилось два поста выше:
    http://code.google.com/p/fasmme/downloads/detail?name=radix.rar&can=2&q=

    Так оно смотрится:
    [​IMG]
     
  14. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Один деятель уже писал в projects свой конвертор. Тот же глюк - где выделение периода дробной части у периодичесиких дробей?
     
  15. edemko

    edemko New Member

    Публикаций:
    0
    Регистрация:
    25 ноя 2009
    Сообщения:
    454
    Цветом?
    Поясни.
    То сами числа такие, так и должно быть.
    Проверял calc.exe, результат ок даже для сомнительного 1/MAXDWORD, когда в EBX:EAX=1(вызов reciprocal_dword).
    Казалось, чего может весить 2^-64:
    calc.exe: 2,3283064370807973754314699618685e-10
    radix.exe: 0.000000000232830643708079

    В самом первом посту спрашивается про замену деления умножением.
    Вот свойсно и оно.
    Чисто в практических целях.
    Трошка дописалось - подсвечивает число сдвигов(замена div).

    Моим мотивом было поделиться.
    По теме буду писать курсовую(нам можно за желанием).

    persicum, вы злы?
     
  16. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    edemko
    :
    5/6 = 0,8(3)
    6/7 = 0,(857142)
    Кстати, мой calc.exe выдаёт иной результат для 2^(-64) = 5,4210108624275221700372640043497e-20 (Windows 7).
     
  17. edemko

    edemko New Member

    Публикаций:
    0
    Регистрация:
    25 ноя 2009
    Сообщения:
    454
    Результат возвращался в ECX:EBX:EAX=2^-32 + 2^-64, записанный как ненормализированное число = двоичная дробь наподобе десятичной.

    KeSqueer,
    Cпасибо за поправку.
    >не отвечать>Простите за наезд стосовно мягких(ь) знаков когда-то.
    dec: 0.000000000232830643708079
    bin: 0.0000000000000000000000000000000100000000000000000000000000000001
    hex: 0.0000000100000001
    shl: 31

    persicum, и что с этим делать?
     
  18. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Например, можно узнать, представимо ли число в двоичном виде (в сопроцессоре) точно или округленно? Например, 0.1?

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