mpz_prevprime

Tue Feb 4 23:59:29 UTC 2020

On mersenneforum there's a prime gap search project. I tried running a
modified version of their search program.
I got VERY VERY VERY lucky and found a prime gap > 2^15 with the 4th
highest merit of *any know prime gap*.
it's a PRP with 404 digits that could replace the 454 digit prime in the
patch. Sadly it will only be 50-100% faster.

Given Marco's timing of 25 seconds (and a goal of say 3 seconds on that
machine) the start prime would need to be ~~200 digits.
The merit of such a prime gap would be 2^15 /ln(10^200) ~= 71.

I plotted the highest merit prime gap by year discovered and fitting a
trendline.
Code here:
https://colab.research.google.com/drive/1kTLxxOToqAsE_md6wGhyN0AVT2DPmasA
The trend line is an increase of ~0.5 merit per year from 2000 to 2020.
So it's unlikely we'll find a prime gap that we can enable in the tests
soon.

I still think there's value in having this test committed (but commented
out) so that people (READ: me) touching the magic constant can run it
one-off.

--Seth

On Thu, Jan 30, 2020 at 2:15 PM Seth Troisi <braintwo at gmail.com> wrote:

>
>
> 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.
>>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Screenshot from 2020-02-03 12-50-19.png
Type: image/png
Size: 17203 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200204/bee76ce8/attachment-0001.png>