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

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

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

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

 

А монтгомери полной редукции не гарантирует, он тока гарантирует отсутствие потери информации при переполнении, что частичный остаток влезет в 32-бит. Так что тут тоже нужен гимор с доводкой числа.

 

Предпоследний вариант кода из #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

Тупость заключается в лишних ветвлениях, для большей скорости их нужно устранить.

 

Ну оптимальное сложение по модулю выглядит совсем по другому. Но вопрос не в этом. Я тоже сначала юзал заглушку на jc. Вопрос, если числа трансформированы, то как складывать? Чистый p выглядит подозрительным

 

похвалялась репа что с медом хороша... FFFOOOOI и сам для сдвигов хорош...

 

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

 

Точно так же, как если они не трансформированы. Нужно просто вычитать p, если результат (с учётом возможного 32-битного переполнения) оказался больше или равен p.

Ага, код из #78 это использует (потому что в коде из #83 можно заметить команду mul ebp, а в ebp хранится p).

 

хм.. столкнулся с мелкой проблемой относительно деления на пять.
подсмотрев трюк у 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.

 

http://www.wasm.ru/baixado.php?mode=tool&id=203

 

murder сенькс, крутая прожка..

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

 

капут

Код (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

 

Код (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

 

Воплотилось два поста выше:
http://code.google.com/p/fasmme/downloads/detail?name=radix.rar&can=2&q=

Так оно смотрится:

 

Один деятель уже писал в projects свой конвертор. Тот же глюк - где выделение периода дробной части у периодичесиких дробей?

 

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

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

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

persicum, вы злы?

 

edemko

:
5/6 = 0,8(3)
6/7 = 0,(857142)
Кстати, мой calc.exe выдаёт иной результат для 2^(-64) = 5,4210108624275221700372640043497e-20 (Windows 7).

 

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

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

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

 

Например, можно узнать, представимо ли число в двоичном виде (в сопроцессоре) точно или округленно? Например, 0.1?

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