View Single Post
Old 2021-01-07, 10:40   #124
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

585810 Posts
Default

Quote:
Originally Posted by SethTro View Post
Not sure I quite understand the question. Is it
1) Why do I always search downwards before upwards?
2) Why do I give up after one search?

1) I don't think it matters which direction you search or if you search the denser / less dense side first.

It's possible there's some better out of order search scheme that alternates testing values on each side and from different points in the sieve but let's ignore that and focus on searching one side till we find the closest prime in that direction; Note this always takes the same expected number of PRP tests minus the small < 0.5% chance that we exceed the sieve length.

My mental justification was: If one side is twice as dense and we search that side first; the expected value is nearer but the sparseness on the other side makes it still likely to find a record. If we search the sparse side first then we get a larger value but the other side is denser so it's similar.

Let me know if this doesn't pass a smell test and we can try to validate by running a post-facto analysis over some run with --no-side-skip.

for 2) I wrote a bit about this at https://github.com/sethtroisi/prime-...ne-sided-tests
To some extent I think it makes sense to try and find one of the end points as that allows for an early skip(as that is done 90% of the time now). I wonder whether skips could be done faster/more frequently/more accurately if a small portion of the other side is also tested early(before aiming for finding an end point). Record gaps very rarely have 90%(optimal figure to be determined based on the records list) on one side so 10% should be tested early on both sides.
henryzz is online now   Reply With Quote