View Single Post
Old 2021-01-08, 05:47   #125
SethTro's Avatar
Apr 2019

10D16 Posts

Originally Posted by henryzz View Post
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.
I've been pondering this for a while and you've changed my mind I should be testing the least dense portion of the interval.

I plotted some examples and it appears that if d the divisor has few divisors (1, 2, 3) the center is clearly less dense but as d has more divisors (6,30,210) it's not clear how much this helps.

I'm not sure how to measure the improvement but I'd guess this would give another 5-15% improvement but would take some reasonable amount of code. I've recorded it in the low priority TODOs but I'm unlikely to write this soon (happy to help anyone interested in coding it up).
Attached Thumbnails
Click image for larger version

Name:	d=6.png
Views:	57
Size:	45.1 KB
ID:	24136   Click image for larger version

Name:	d=30.png
Views:	58
Size:	48.9 KB
ID:	24137  
SethTro is offline   Reply With Quote