Would someone mind elaborating the explanation in the manual?
cic_3_b at yahoo.com
Sat Oct 25 06:43:08 CEST 2003
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.
--- 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
> > 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
> 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
> 23, 29, and 31 than it is to check bignum for divisibility by those
> 3 numbers. There's a cost in calculating R in the first place, but
> 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
> small integers for which divisibility needs to be tested. (If it
> me, I'd want to do some timings to check .... I'm a little dubious
> you'll find a saving for only 2 small test divisors).
> I've also seen literature (not specifically relating to GMP)
> that you could simply calculate the gcd of bignum and 20677 - or
> 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
> don't know how that method stacks up (speed-wise) against the above
Live with it
Do you Yahoo!?
The New Yahoo! Shopping - with improved product search
More information about the gmp-discuss