mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Prime Gap Searches

Reply
 
Thread Tools
Old 2021-08-02, 20:54   #133
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

22×7×13 Posts
Default

Dana's code always tests low side first, then high side. My code does the same thing (always testing the low side first). Even if one side is significantly more dense.

For large numbers (>5000 digits) where PRP take significant amounts of time, these are all theoretical optimizations to find large gaps faster.


1. Calculating

<br />
P(\text{record gap} \mid sieve)<br />

And skipping intervals where the probability is small (e.g. the both sides are more dense with unknowns than expected).


2. Calculating

<br />
P(\text{record gap} \mid \text{upper sieve, lower gap})<br />

Skipping finding the 2nd surrounding prime when the first prime is nearby.


3. Calculating

\sum{P(\text{lower gap}) * H(P(\text{record gap} \mid \text{upper sieve, lower gap}) < \text{skip prob})}<br />
vs
\sum{P(\text{upper gap}) * H(P(\text{record gap} \mid \text{lower sieve, upper gap}) < \text{skip prob})}

This would be more time consuming, roughly O(n^2) vs O(n), but would tell us which side (upper / lower, next / previous) is more likely to result in skipping. A newer calculation shows this gives only a 0-3% speedup and requires a LOT of extra code.


Dana's code implements 1, my code implements 1 and 2. I would not recommend optimization 3 in practice.

Last fiddled with by robert44444uk on 2021-08-04 at 14:24
SethTro is offline   Reply With Quote
Old 2021-08-04, 14:24   #134
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

19×103 Posts
Default

Quote:
Originally Posted by SethTro View Post
Dana's code always tests low side first, then high side. My code does the same thing (always testing the low side first). Even if one side is significantly more dense.

Danaj's surround_primes code also allows for a limited range to be checked (delta). As deficient primorials have very few prime candidates within 2 normal gap widths (and sometimes 4 times) from the centre, then there is little cost in carrying out this check. This would then eliminate those candidates where the plus side has a prime within 2 or 4 widths of the centre point.

Last fiddled with by robert44444uk on 2021-08-04 at 14:26
robert44444uk is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Basic Number Theory 4: a first look at prime numbers Nick Number Theory Discussion Group 6 2016-10-14 19:38
Before you post your new theory about prime, remember firejuggler Math 0 2016-07-11 23:09
Mersene Prime and Number Theory Ricie Miscellaneous Math 24 2009-08-14 15:31
online tutoring in prime number theory jasong Math 3 2005-05-15 04:01
Prime Theory clowns789 Miscellaneous Math 5 2004-01-08 17:09

All times are UTC. The time now is 18:56.


Sun Oct 17 18:56:00 UTC 2021 up 86 days, 13:24, 0 users, load averages: 1.65, 1.48, 1.45

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.