For my own mathematical project, I need the remainder of a division by some prime numbers (7, 13, 19, etc...).
The division is in multiprecision (more than 64 bits).
Here is how I perform the computation of the modulo 7:
xor edx, edx
mov ebx, 7
n = PRECISION*4
rept PRECISION
n = n-4
mov eax,
div ebx
endm
mov eax, edx
Eax now contains (Ptr1 % 7)
I have been told that faster methods may exist (floating point multiplication by 1/7, etc...).
Can someone improve this ?
This is REALLY important !!!
JCM
The division is in multiprecision (more than 64 bits).
Here is how I perform the computation of the modulo 7:
xor edx, edx
mov ebx, 7
n = PRECISION*4
rept PRECISION
n = n-4
mov eax,
div ebx
endm
mov eax, edx
Eax now contains (Ptr1 % 7)
I have been told that faster methods may exist (floating point multiplication by 1/7, etc...).
Can someone improve this ?
This is REALLY important !!!
JCM
http://swox.com/gmp/manual/Exact-Remainder.html#Exact%20Remainder
...there is some asm code in the GMP source.
You just have to convert it to MASM syntax.
...there is some asm code in the GMP source.
You just have to convert it to MASM syntax.
http://swox.com/gmp/manual/Exact-Remainder.html#Exact%20Remainder
...there is some asm code in the GMP source.
You just have to convert it to MASM syntax.
Now, I see how to do it very quickly.
Instead of cutting the number in 32 bits, and compute:
N=a * 2^32 + b
(((a * 2^32) mod 7) * 2^32 + b) mod 7
2 divisions
I can cut it in 16 bits, and compute as follows:
N=a*2^48 + b*2^32 + c*2^16 + d
((a) + (b * 4) + (c * 2) + (d)) mod 7
1 division !
since
2^48 mod 7 = 1
2^32 mod 7 = 4
2^16 mod 7 = 2
JC
MMX? :)
movq mm0,[qword Ptr1]
pmaddwd mm0,[n0001000400020001]
pshufw mm1,mm0,1110b
paddd mm0,mm1
xor edx,edx
movd eax,mm0
div [n7]
Nexo, very nice. :) I've just started using the SSE stuff and I'm amazed at how handy some of those instructions are. You demonstrate the powers of PSHUFW and PMADDWD very nicely.