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 <brain...@gmail.com> wrote: > > > On Thu, Jan 30, 2020 at 6:23 AM Niels Möller <ni...@lysator.liu.se> wrote: > >> 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). >> >> > (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. >> >
_______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
