Would someone mind elaborating the explanation in the manual?
Brian Hurt
bhurt at spnz.org
Sat Oct 25 13:06:23 CEST 2003
On Fri, 24 Oct 2003, David McKen wrote:
> In the efficiency section of the GMP manual I came across the
> following couple lines
>
> --Begin quote--
> However when testing divisibility by several small integers, it's
> best to take a remainder modulo their product, to save
> multi-precision operations. For instance to test whether a number is
> divisible by any of 23, 29 or 31 take a remainder modulo 23*29*31 =
> 20677 and then test that.
> --End quote--
>
> Needless to say I don't understand this. Does someone have either a
> web site that has the formulas describing this process (also if
> possible a proof) or some example code that achieves this purpose?
int foo(mpz_t x) {
/* Returns 1 if x is divisible by 23, 29, or 31 */
unsigned long m = mpz_fdiv_ui(x, 23ul * 29ul * 31ul);
if (((m % 23) == 0) || ((m % 29) == 0) || ((m % 31) == 0)) {
return 1;
} else {
return 0;
}
}
Assume we're interested in prime p. We know that x mod (p * k) = m for
some k. In other words, we know that x = t * (p * k) + m for some t. If
m mod p = 0, i.e. m = u * p for some u, then x = t * (p * k) + (u * p) =
(t * k + u) * p, which means that x mod p = 0.
This is a speed up because compared to doing a long mod long, doing a
mpz_t mod long is expensive. The above code is almost 3x as fast as the
naive implementation:
int foo(mpz_t x) {
if ((mpz_fdiv_ui(x, 23ul) == 0ul) || (mpz_fdiv_ui(x, 29ul) == 0ul)
|| (mpz_fdiv_ui(x, 31ul) == 0ul))
{
return 1;
} else {
return 0;
}
}
Brian
More information about the gmp-discuss
mailing list