mpz_prevprime

[Niels Möller]

tg at gmplib.org (Torbjörn Granlund) writes:

> We have tried to stick to a limit of 1 s on a reasonable current
> computer. Most tests should use much less, if possible.

Maybe it would make sense with a command line option or environment
variable to the test binaries to enable certain more expensive tests
(rather than just tweaking the number of repetitions).

nextprime.c includes the loop

#define INCR_LIMIT 0x10000 /* deep science */

      for (difference = incr = 0; incr < INCR_LIMIT; difference += 2)

where it's a bit challenging to quickly test the case of the loop
running to the end. I think the test changes by Seth
(https://github.com/sethtroisi/libgmp/pull/12/commits/7e884d040d94346bb8428e99a3d64d30f3701f3a)
adds test coverage for this particular condition. According to comments,

  // This takes ~3 seconds
  // Gap 33008 from P454 = 55261931 * 1063#/210 - 13116

I don't know the distribution of primegaps, but to make the test run
fast, we'd want a gap where as many as possible of the composites in the
interval have some really small factor, to minimize the number of calls to
mpz_millerrabin within the loop.

Perhaps one can use crt to construct a number k such that

k      = 1 (mod 2)  ; k odd 
k      = 0 (mod 3)
k + 2  = 0 (mod 5)
k + 4  = 0 (mod 7)
k + 6  = 0 (mod 3)  ; redundant
k + 8  = 0 (mod 11)
k + 10 = 0 (mod 13)
k + 12 = 0 (mod 5)  ; redundant

etc ? How big gap would that give us, if we used all the tabulated
primes? (The current prime list includes 167 primes, that number
probably based on long obsolete benchmarks).

I imagine the function could also be generally sped up a bit by
increasing the size of prime list and using tabulated 2-adic inverses
for the divisibility checks.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.