Re:1.5 is the midpoint between 0 and infinity in Ruby
by MauranKilom on Friday November 27, 2020 @05:41AM
(#25227445)
> they could get rid of it by bisecting on [1/n; n] instead of [0; n], as they already know that 1/n (and numbers lower than 1/n) isn't a valid candidate from the first step.
Did you mean [n/2; n]?
Re:1.5 is the midpoint between 0 and infinity in Ruby
by progval on Friday November 27, 2020 @08:56AM
(#25228715)
Oops, yes, I did.
Re:1.5 is the midpoint between 0 and infinity in Ruby
by ashtonkem on Friday November 27, 2020 @04:51PM
(#25232890)
Interestingly, they're doing unnecessary work here. In this case, the algorithm has already checked 32, so there's no need to check again.
In fact, if you're checking N, it's guaranteed that N/2 has already been checked, and the next best step should be (3/4)N; in this case 48.
With infinite ranges, you can't do that; so the usual way is to start with a small number and increase exponentially until you find a number that is too large; which is what is done here. When you got that number, it becomes the upper bound of a finite interval.
So that's a two step process, which we can see here. The first 32 is in the exponential growth step (so is 64), and the second one is in the bisect step.
This will always happen exactly once (unless the expected result is 0) and for only the first pivot in the bisect, so it's not that bad; but indeed, they could get rid of it by bisecting on [1/n; n] instead of [0; n], as they already know that 1/n (and numbers lower than 1/n) isn't a valid candidate from the first step.