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
Posted on 2002-06-05 04:51:27 by MCoder
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.
Posted on 2002-06-05 06:18:28 by bitRAKE

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
Posted on 2002-06-05 10:00:31 by MCoder
MMX? :)


movq mm0,[qword Ptr1]
pmaddwd mm0,[n0001000400020001]
pshufw mm1,mm0,1110b
paddd mm0,mm1
xor edx,edx
movd eax,mm0
div [n7]
Posted on 2002-06-05 13:49:36 by Nexo
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.
Posted on 2002-06-05 13:59:19 by bitRAKE