Would someone mind elaborating the explanation in the manual?

[David McKen]

Ahh well now that makes sense.

What I am trying to do is factor a number so the more of the small
primes that I can test for divisibility the less time I waste trying
numbers that simply won't divide into my number.

Thank you for your time Rob.

Signed
David McKen


--- Sisyphus <kalinabears at iinet.net.au> wrote:
> 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--
> > 
> 
> It's telling you to calculate R = bignum % 20677, and to then check
> R 
> for divisibility by 23, 29, and 31.
> 
> That will work because if x divides bignum, x also divides
> bignum % (x * a) for all non-zero integers a.
> And if x does not divide bignum, x does not divide
> bignum % (x * a) for any non-zero integer a.
> 
> It will be quicker because it is faster to check R for divisibility
> by 
> 23, 29, and 31 than it is to check bignum for divisibility by those
> same 
> 3 numbers. There's a cost in calculating R in the first place, but
> that 
> cost is more than offset by the savings.
> 
> At least, that's how I'm reading it. As to whether there's a saving
> 
> would, I think, depend upon the size of bignum, and upon the number
> of 
> small integers for which divisibility needs to be tested. (If it
> were 
> me, I'd want to do some timings to check .... I'm a little dubious
> that 
> you'll find a saving for only 2 small test divisors).
> 
> I've also seen literature (not specifically relating to GMP)
> suggesting 
> that you could simply calculate the gcd of bignum and 20677 - or
> you 
> could extend that to calculating the gcd of R and 20677. You have
> to be 
> a little careful there if the "small" numbers are not primes - and
> I 
> don't know how that method stacks up (speed-wise) against the above
> 
> recommendation.
> 
> Hth.
> 
> Cheers,
> Rob

=====
Signed 
David Mcken

Life Sucks
Live with it

__________________________________
Do you Yahoo!?
The New Yahoo! Shopping - with improved product search
http://shopping.yahoo.com