View Single Post
Old 2020-10-28, 21:41   #100
SethTro's Avatar
Apr 2019

3×7×13 Posts
Default Do less work, find more records

I've have recently doubled my rate of finding records with two tricks.

I have a new algorithm that speeds up sieving by ~10,000x. This means deeper sieving meaning fewer PRPs. I have two additional tricks that also give a huge speed advantage.

For each 'm' I calculate prob(record gap) given the results of deep sieving, this forms a distribution (see attachment bottom row). I only test records from the top ~20% (why waste time on 'm' with low chance of finding a record).

Once I have an m with high prob(record gap) I find prev_prime and recalculate prob(record gap | prev prime), 90% of the time prob(record gap | prev prime) < prob(record gap) / 2 so I skip finding next_prime as the chance of record is lower than going to the next m. I get (.1 * prob(record) + .9 * .75 * prob(record)) / (.1 * 2 + .9 * 1) => 70% of the prob(record) in covered in 50% of the time, in practice it's even better because the faster prev_prime are more likely to skip so the denominator is more like (0.1 * (1.5 + 1) + .9 * 0.5).

These tricks mean that I'm finding ~54 records / day vs ~25 records / day (testing all m, both sides).
Attached Thumbnails
Click image for larger version

Name:	3001_2190_1_100000_s40000_l10000M.txt.comb.png
Views:	68
Size:	293.2 KB
ID:	23662  
SethTro is offline   Reply With Quote