Optimizing Modulus (was Re: Would someone mind elaborating the
explanation in the manual?)
Niels Möller
nisse at lysator.liu.se
Tue Oct 28 08:09:29 CET 2003
David McKen <cic_3_b at yahoo.com> writes:
> At the moment I am at a loss for optimizations as I have already
> optimized this program from iterating at 1333+ times a second to the
> current lower bound of it's potential at 300,000+.
Do I understand you correctly that you want to search for numbers that
have no small factors? One way of doing this (which is implemented but
#if:ed out in the mpz/nextprime.c file) is as follows:
Use a precomputed table of the first B odd primes p_k (B could be
somewhere in the range 10-10000, each p_k should fit in a single
limb). Input is an odd number n. This algorithm returns the smallest
number >= n which is not divisible by any of the primes p_k:
for k=0, ..., B-1,
m_k = n mod p_k
d = 0
while some m_k = 0
d = d + 2
for k = 0, ... B-1
m_k = (m_k + 2) % p_k
return n + d
The idea is that the inner loop updates only B single-limb moduli,
where for each moduli you need do an add, a comparison and a
conditional subtraction.
It's possible (but unlikely) that you will loop around so many times
that d doesn't fit in a limb, so one should check for this case and
when needed update n and reset d: n = n + d, d = 0.
If you try this method, I'm very curious to know what's a reasonable
values of B, for good performance.
/Niels
More information about the gmp-discuss
mailing list