2021-08-02, 20:54 | #133 |
"Seth"
Apr 2019
2^{2}·97 Posts |
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 And skipping intervals where the probability is small (e.g. the both sides are more dense with unknowns than expected). 2. Calculating Skipping finding the 2nd surrounding prime when the first prime is nearby. 3. Calculating vs 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 |
2021-08-04, 14:24 | #134 |
Jun 2003
Oxford, UK
3×661 Posts |
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 |
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 |