mpz_prevprime

[Seth Troisi]

On Thu, Jan 30, 2020 at 6:23 AM Niels Möller <nisse at lysator.liu.se> wrote:

> 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).
>
>
(please excuse my casual tone, I'm writing quickly at work)
This technique has already been made use of in generating this number.
1063# = primorial(1063) causes many of the nearby numbers to be divisible
by small primes.
Of the 33008 composite numbers to test in this gap, ~1750 (~5.3%) survive a
sieve of the first 180 primes. This is far better than the average (~8%).

It's easy to generate gaps with far fewer tests, the downside is that the
resulting number is sufficiently larger that I don't believe you'll save
time.
Looking at the speed graph it looks increasing the size of a number ~30% is
a 2x slow down (so you'd have to avoid half of the remaining primality
tests).
Additionally great effort was already but into finding this number (I
pulled it from Dr. Nicely's prime gap merit list) so it's unlikely that I
can easily find a number
with a gap this size with fewer prime tests.



> 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.

This was discussed previously in this thread
https://gmplib.org/list-archives/gmp-devel/2019-September/005465.html
TL;DR >95% of time is spent in miller rabin.


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