braintwo at gmail.com
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
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
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
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
>> 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
> 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
> 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
> TL;DR >95% of time is spent in miller rabin.
>> 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
Size: 17203 bytes
Desc: not available
More information about the gmp-devel