t...@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.
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
