mersenneforum.org CRT offsets
 Register FAQ Search Today's Posts Mark Forums Read

2021-05-06, 23:10   #34
SethTro

"Seth"
Apr 2019

22·7·13 Posts

Quote:
 Originally Posted by CraigLo I took another look at the CRT offsets. I was surprised by how much worse the CRT_6727 did at finding 220k gaps even though it had significantly fewer remaining candidates. We have CRT offsets with 6776, 6751, and 6727 remaining candidates. There is a 4th that was optimized for a merit of 15 that has 6840 remaining candidates. These are all variations on 7993#/13# so I added a fifth to the test, 2347*7993#/13# with 6850 remaining candidates. The ranking based on probability of finding a gap>220k is OPT_15, 7993#/13#, 6776, 6751, 6727 with 6727 significantly worse than the others. The rankings are almost the inverse of the number of candidates remaining.
I coded up this and a lot more for gap_stats where I dynamical calculate the odds that each offset is part of a prime record. It was the next logical step in the optimization for me; technically this makes my code ~20% faster to find record gaps, but the naive code captures ~70% of that benefit so it's a smaller gain and took hundreds of hours of meticulous coding and debugging.

pseudo code is

Code:
For m in range(1, 10^9):
N = m * P#/K

prob_record = 0
for x_i, x in (N + x | no small factors)
for y_i, y in (N - y | no small factors)
if record[x+y] > N:
prob_record += prob_prime ^ 2 + (1- prob_prime) ^ (x_i + y_i)
sadly it's slightly less useful than expected. I found that I was often sieving less than half the distance to the smallest possible records so I had to augment both side with a list of numbers coprime to P#/K

I included a picture from N = m * 1511# / 312270.

"extended^2" looks at records that would be outside on both sides of the sieve.
"extended" refers to records that inside "sieve length" (distance on one side of N sieved) on one but not the other side.

In this example. till you sieve 20K (~13merit) on each side it's hard to judge the probability of a record (min merit ~24) based on just the sieve; you have to look at number of candidates + look outside one or two sides of the sieve.

The second and third graph tell us that the variance (the chance any given m is a record) as sieve length increases up to a 25,000 (16Merit)

I spent ~100 hours trying to understand why the probability decreases in the transition from extended to direct computation. Intuitively the average probability that an interval is a record prime gap is roughly the same before and after we sieve it (some get more likely, some get less likely). I think my code doesn't account for some asymmetry (e.g. if m%3 = 1 then upper and lower gap can't both be % 3 == 2), I'm incorrectly computing something, or ???.
Attached Thumbnails

 2021-05-08, 21:29 #35 CraigLo   Mar 2021 53 Posts Attached is a plot showing the probability that a number is included in a gap of 220k for 2347*2993#/13#. The blue plot is the actual curve. The orange curve is the function exp(-(abs(x/220000))^3.3*5.8). I used the curve fit and calculated a score for each of the offsets. The score is the sum of the probability for each remaining candidate in the interval +/- 220k. Code: Offset Remaining Score Prob>220k CRT_OPT15 6840 7536 7.30E-6 2347*7993#/13# 6850 7545 7.13E-6 CRT_6776 6776 7581 6.92E-6 CRT_6751 6751 7601 6.83E-6 CRT_6727 6727 7704 5.99E-6 The score computed this way properly ranks the candidates based on probability of finding a gap > 220k. I think this approach can be used for finding the best CRT offset, but the function used will change based on the primorials. Attached Thumbnails
 2021-05-09, 08:43 #36 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 61·97 Posts Are you suggesting that we search m*2347*7993#/13#?
2021-05-10, 16:15   #37
CraigLo

Mar 2021

5310 Posts

Quote:
 Originally Posted by henryzz Are you suggesting that we search m*2347*7993#/13#?
That is the best if you limit the optimization to A*7993#/13#. These were easy for me to check.

The one you called optimized for merit 15 (or 20) is a bit better. We can probably do even better.

2021-05-10, 16:49   #38
CraigLo

Mar 2021

1101012 Posts

Quote:
 Originally Posted by SethTro I coded up this and a lot more for gap_stats where I dynamical calculate the odds that each offset is part of a prime record. It was the next logical step in the optimization for me; technically this makes my code ~20% faster to find record gaps, but the naive code captures ~70% of that benefit so it's a smaller gain and took hundreds of hours of meticulous coding and debugging.
That's interesting. I hadn't considered using this to choose best offsets after sieving. At the moment I am just thinking about finding the best offset (x) so that A*P# + x gives the best chance of finding a large gap.

I'm not sure how much time is spent computing the prob_record but you might be able to speed it up using the approach I described above (post 35). You wouldn't be computing probabilities any more but if you just wanted the best offsets it might be useful.

Quote:
 Originally Posted by SethTro I spent ~100 hours trying to understand why the probability decreases in the transition from extended to direct computation. Intuitively the average probability that an interval is a record prime gap is roughly the same before and after we sieve it (some get more likely, some get less likely). I think my code doesn't account for some asymmetry (e.g. if m%3 = 1 then upper and lower gap can't both be % 3 == 2), I'm incorrectly computing something, or ???.

I noticed an effect similar to what you describe once. Take a simple case where the probability of a number being prime is 1%. The probability of no primes in 200 consecutive numbers is

0.99^200 = 0.1340

Now if we sieve and remove 90% of these there are only 20 possible primes left and the probability of a prime is 10%. The probability of no primes is now

.9^20 = 0.1216

Sieving shouldn't change the probability of no primes. We can rewrite the above as

0.99^200 = (0.99^10)^20

For the probability of the gap to stay the same we would need the probability a number is not prime to be 0.99^10 = .9044.