Optimizing Modulus (was Re: Would someone mind elaborating the explanation in the manual?)

[Niels Möller]

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