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

А для суммы двух регистров по модулю нельзя ли код изобразить? Что то у меня получается что нужно маскировать два раза...

 

Может быть так

Код (Text):

1. x dd ?
2. y dd ?
3. ....
4. movq   mm1,qword[x]
5. movq   mm0,qword[x]   ;mm0 = y | x
6. psrad  mm1,31
7. pxor   mm0,mm1        
8. psubd  mm0,mm1        ;mm0 = abs(y) | abs(x)
9. pshufw mm1,mm0,1110b  ;mm1 = abs(y)
10. paddd  mm0,mm1        ;mm0 = abs(x)+abs(y)
11. movd   eax,mm0        ;eax - ответ

А лучше весь алгоритм переписать на MMX

 

По любому я буду писать код в трех вариантах, для ALU, MMX и SSE2. Еще наверное круче смешивать MMX и SSE2, но это я не умею и не практикую.
Не совсем уверен, то ли это что нужно...
Это я опять про голимые остатки. Типа

Код (Text):

1. add eax, edx
2. jnc .skip1
3. sub eax, F3000001
4. .skip1
5. cmp eax, F3000001
6. jb .skip2
7. sub eax, F3000001
8. .skip2

Пока юзаю этот наивный код, потом буду чистить от JMP

 

Может преобразовать этот код с применением метода дихотомии (сложность O(log2n))? Но в таком случае будут применяться большие таблицы (размер таблицы зависит от максимальной возможной суммы).

 

Mikl___

Прошу прошения, F3000001 конечно допускает упрощенное взятие остатка, но не до такой степени просто, как FFF00001. Теперь я работаю по модулю именно FFF00001. Миллион точек должно хватить для FFT. Есть еще второе число на 32 бит в запасе подобной Мерсено-Ферматной структуры с тремя весами.

Вот и задачка вырисовывается - мгновенное взятие остатка (по модулю) FFF00001. Причем DIV и MUL точно не нужны, можно видимо на одних шифтах.

 

Я подозреваю что все эти асмерские шняги пригодны главным образом только для стандартных типов, а если нужно поделить 64-бит на 32-бит то лучше DIVа ничего не придумаешь?

А самый лучший способ избавиться от делений это считать по модулю чисел Ферма, Мерсена и их обобщений. Никаких тебе делений и даже умножений не нужно в этом случае. Ну што там у нас с FFF00001 ?

 

Mikl___, murder, ку-ку, where you at?

На данный момент я нашел следующую неуклюжую конструкцию

Код (Text):

1. mul edx
2.  
3. @loop:
4. mov ecx,eax
5. mov eax,2^32-Prime
6. mul edx
7. add eax,ecx
8. adc edx,0
9. jnz @loop
10.  
11. sub eax,Prime
12. sbb edx,edx
13. and edx,Prime
14. add eax,edx

С шифтами мне не удалось получить хороших результатов, шифты очень ценятся при разработке микросхем, а на PC и MUL сам по себе весьма неплох. Так вот, это код работает в 1.7 раза быстрее взятия остатка через один-единственный DIV. Это просто невероятно, до чего же DIV чудовищно-тормозная команда!

 

persicum
Если честно - ничего не понял.
Это что? Взятие остатка от деления на константу для 64-битных чисел?

Попробуй так

Код (Text):

1. fild  [divider]
2. fild  [value]
3. fprem
4. fistp [reminder]
5. fstp  st(0)

AMD пишет, что fprem занимает 9+e+n тактов. Что бы это могло значить?

 

Ага, остаток от деления 64-bit на константу 32-bit, coвершенно верно. Может быть полезно для криптографии и кодирования. Поскоку я в плавучке х87 совсем не соображаю, то можно плиз полный код на входе edx, eax, на выходе еах? Чтоб в память не лазить? А я тогда побенчу.

На выходе в eax остаток от деления произведения edx*eax на константу

 

С FPU это невозможно Все действия через память.

В том коде
divider - делитель
value - делимое
reminder - остаток

 

Неушта нельзя еах запихнуть в стек сопроцессора прямиком?

 

persicum
Ничего не поделаешь

 

А и SIMD нет командочки похожей на fprem?

 

murder
А не лажа ли этот fprem? 64 раза вычитает а потом отваливается... Это только частичный остаток.

 

Действительно. Вот, что про неё пишут

 

Развивая идею из поста №24 написал такое

Код (Text):

1. var
2.   divider: array [0..32] of int64=($FFF00001,
3.                                    $1FFE00002,
4.                                    $3FFC00004,
5.                                    $7FF800008,
6.                                    $FFF000010,
7.                                    $1FFE000020,
8.                                    $3FFC000040,
9.                                    $7FF8000080,
10.                                    $FFF0000100,
11.                                    $1FFE0000200,
12.                                    $3FFC0000400,
13.                                    $7FF80000800,
14.                                    $FFF00001000,
15.                                    $1FFE00002000,
16.                                    $3FFC00004000,
17.                                    $7FF800008000,
18.                                    $FFF000010000,
19.                                    $1FFE000020000,
20.                                    $3FFC000040000,
21.                                    $7FF8000080000,
22.                                    $FFF0000100000,
23.                                    $1FFE0000200000,
24.                                    $3FFC0000400000,
25.                                    $7FF80000800000,
26.                                    $FFF00001000000,
27.                                    $1FFE00002000000,
28.                                    $3FFC00004000000,
29.                                    $7FF800008000000,
30.                                    $FFF000010000000,
31.                                    $1FFE000020000000,
32.                                    $3FFC000040000000,
33.                                    $7FF8000080000000,
34.                                    $FFF0000100000000);
35.   value: int64;
36.   i:     dword;
37.  
38. implementation
39.  
40. {$R *.dfm}
41.  
42. procedure TForm1.FormCreate(Sender: TObject);
43. begin
44. randomize;
45. value:=random(5454545121798);
46. asm
47. mov  edx,dword[value+4]
48. xor  ecx,ecx
49. bsr  ecx,edx
50. sete dl
51. inc  ecx
52. sub  cl,dl
53.  
54. mov  eax,dword[value]
55. mov  edx,dword[value+4]
56. @1:
57.     sub  eax,dword[divider+ecx*8]
58.     sbb  edx,dword[divider+ecx*8+4]
59.   jnl @1
60.   add eax,dword[divider+ecx*8]
61.   adc edx,dword[divider+ecx*8+4]
62.   dec ecx
63. jnl @1
64. mov i,eax
65. end;
66. form1.Caption:=inttostr(i)+'='+inttostr(value mod $FFF00001);
67. end;

 

То есть ты предлагаешь вызывать fprem или просто вычитать это дело 32 раза, заглядывая в таьлицу 32 раза? Можно сделать с двумя таблами на 64 К входов и заглядывать в них всего по разу, но не факт что это быстрее будет умножений в цикле, как у меня. Замеры можно?

 

и еще, задачка не в том чтобы сымитировать DIV на машине где его нету, задача в том чтобы обогнать его там где он есть и хорошо работает. Табличные методы универсальны и пригодны для любой константы, а тут у нас редукция идет по формуле
d*2^32 + a = a + d*2^20 - d

 

Сложность алгоритма O(log2n)

Вот функция взятия 64-битного остатка от деления из AMD Code Optimization guide

Код (Text):

1. ;[ESP+8]:[ESP+4] делимое
2. ;[ESP+16]:[ESP+12] делитель
3. ;EDX:EAX остаток
4. _ullrem:
5. PUSH    EBX ;save EBX as per calling convention
6. MOV ECX, [ESP+20]   ;divisor_hi
7. MOV EBX, [ESP+16]   ;divisor_lo
8. MOV EDX, [ESP+12]   ;dividend_hi
9. MOV EAX, [ESP+8]    ;dividend_lo
10. TEST    ECX, ECX    ;divisor > 2^32–1?
11. JNZ .r_big_divisor  ;yes, divisor > 32^32–1
12. CMP EDX, EBX    ;only one division needed? (ECX = 0)
13. JAE @f  ;need two divisions
14. DIV EBX ;EAX = quotient_lo
15. MOV EAX, EDX    ;EAX = remainder_lo
16. MOV EDX, ECX    ;EDX = remainder_hi = 0
17. POP EBX ;restore EBX as per calling convention
18. RET
19. @@:
20. MOV ECX, EAX    ;save dividend_lo in ECX
21. MOV EAX, EDX    ;get dividend_hi
22. XOR EDX, EDX    ;zero extend it into EDX:EAX
23. DIV EBX ;EAX = quotient_hi, EDX = intermediate remainder
24. MOV EAX, ECX    ;EAX = dividend_lo
25. DIV EBX ;EAX = quotient_lo
26. MOV EAX, EDX    ;EAX = remainder_lo
27. XOR EDX, EDX    ;EDX = remainder_hi = 0
28. POP EBX ;restore EBX as per calling convention
29. RET
30. .r_big_divisor:
31. PUSH    EDI ;save EDI as per calling convention
32. MOV EDI, ECX    ;save divisor_hi
33. SHR EDX, 1  ;shift both divisor and dividend right
34. RCR EAX, 1  ;by 1 bit
35. ROR EDI, 1
36. RCR EBX, 1
37. BSR ECX, ECX    ;ECX = number of remaining shifts
38. SHRD    EBX, EDI, CL    ;scale down divisor and dividend such
39. SHRD    EAX, EDX, CL    ;that divisor is less than 2^32
40. SHR EDX, CL ; (i.e. fits in EBX)
41. ROL EDI, 1  ;restore original divisor (EDI:ESI)
42. DIV EBX ;compute quotient
43. MOV EBX, [ESP+12]   ;dividend lo-word
44. MOV ECX, EAX    ;save quotient
45. IMUL    EDI, EAX    ;quotient * divisor hi-word (low only)
46. MUL DWORD [ESP+20]  ;quotient * divisor lo-word
47. ADD EDX, EDI    ;EDX:EAX = quotient * divisor
48. SUB EBX, EAX    ;dividend_lo – (quot.*divisor)–lo
49. MOV ECX, [ESP+16]   ;dividend_hi
50. MOV EAX, [ESP+20]   ;divisor_lo
51. SBB ECX, EDX    ;subtract divisor * quot. from dividend
52. SBB EDX, EDX    ;(remainder < 0)? 0xFFFFFFFF : 0
53. AND EAX, EDX    ;(remainder < 0)? divisor_lo : 0
54. AND EDX, [ESP+24]   ;(remainder < 0)? divisor_hi : 0
55. ADD EAX, EBX    ;remainder += (remainder < 0)?
56. ADC EDX, ECX    ;divisor : 0
57. POP EDI ;restore EDI as per calling convention
58. POP EBX ;restore EBX as per calling convention
59. RET

 

murder, а не переписать ли Вам код из поста н27 на SSE2? Так Вы бы могли внести свой вклад в мою прогу и навечно вписать в мануал свой ник золотыми буквами...
Я очень разбалован флагами и не представляю как там на SSE2 чегото сравнивать и ловить переполнения, но любителям Уоренна это не сложно. В общем, редукцию в цикле нужно будет делать для двух пар чисел по очереди, а окончательную редукцию можно сделать запихнув все в один регистр xmm.

В общем процедура принимает
abcd и efgh,
а возвращает ijkl
где
i=(a*e) mod fff00001
j=(b*f) mod fff00001
и т.д.