View Single Post
Old 2020-10-29, 08:05   #103
robert44444uk's Avatar
Jun 2003
Oxford, UK

1,933 Posts

Originally Posted by SethTro View Post
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).
Hi Seth

It would be useful, in this and your other post, #98 if you could explain your variables - so what is "m", "d", "p" "X" - generally, for deficient primorial multiples we have tended to use the convention k*p#/d , n*p#/d or A*p#/d but actually it does not matter what you use as long as it is explained. It is also helpful to provide a small worked example where this helps understanding.

Which language are you developing the sieve in? On this group we have tended to use perl, because of dana's work providing Perl solutions for sieves, surround_primes and prev_prime and next_prime. or c++ where c++ coded programs have been made executables.

But we are all interested in something that speeds up a sieve 10000 times :) Your results pickup is impressive.
robert44444uk is offline   Reply With Quote