1.5 is the midpoint between 0 and infinity in Ruby
blog.peterzhu.ca
1.5 is the midpoint between 0 and infinity in Ruby
1–10 of 125 posts
Re: 1.5 is the midpoint between 0 and infinity in Ruby
#2"if x and y are doubles and x > y, then we have shown that double_as_int64(x) > double_as_int64(y)"
This only applies for numbers of the same sign though. As soon as the sign changes, the relation breaks since floating point numbers use an independent sign bit while int64 is 2's complement.
Re: 1.5 is the midpoint between 0 and infinity in Ruby
#3"if x and y are doubles and x > y, then we have shown that double_as_int64(x) > double_as_int64(y)" This only applies for numbers of the same sign though. As soon as the sign changes, the relation breaks since floating point numbers use an independent sign bit while int64 is 2's complement.
double_as_int64 as defined in the linked source code does take care of the sign so that double_as_int64(x) == -double_as_int64(-x). This is also important for the negative zero case.
Re: 1.5 is the midpoint between 0 and infinity in Ruby
#4Maybe it isn't wrong after all. Two uncountable infinities are equal!
Re: 1.5 is the midpoint between 0 and infinity in Ruby
#5Meta: what is the time between the same URLs being considered unique posts on HN now? I think it was 24 hours back in the old days, but seems to be somewhat less now as the post's author submitted it only 9 hours ago: https://news.ycombinator.com/item?id=25224627 :-)
Re: 1.5 is the midpoint between 0 and infinity in Ruby
#6Maybe it isn't wrong after all. Two uncountable infinities are equal!
Sorry but they are not, power set of R is bigger than R.
Re: 1.5 is the midpoint between 0 and infinity in Ruby
#7 The following values were inspected:
1
2
4
8
16
32
64
32
48
40
44
42
43
Re: 1.5 is the midpoint between 0 and infinity in Ruby
#8The following values were inspected: 1 2 4 8 16 32 64 32 48 40 44 42 43 The most surprising part for me is that in the integer search 32 is inspected twice. From my brief testing it seems to only happen with infinite ranges. Is that a bug in bsearch or am I missing something?
It shouldn't be a problem but technically you are right that Ruby does one more comparison than needed. My guess is that it would mean to keep the previous value of mid (as in `bsearch_integer_range(prev_mid, mid, 0)` instead of the current `bsearch_integer_range(beg, mid, 0)`) and that might be annoying to do in C.
Re: 1.5 is the midpoint between 0 and infinity in Ruby
#9The following values were inspected: 1 2 4 8 16 32 64 32 48 40 44 42 43 The most surprising part for me is that in the integer search 32 is inspected twice. From my brief testing it seems to only happen with infinite ranges. Is that a bug in bsearch or am I missing something?
With a finite range, you can bisect directly by splitting in the middle of the range.
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.
Re: 1.5 is the midpoint between 0 and infinity in Ruby
#10The following values were inspected: 1 2 4 8 16 32 64 32 48 40 44 42 43 The most surprising part for me is that in the integer search 32 is inspected twice. From my brief testing it seems to only happen with infinite ranges. Is that a bug in bsearch or am I missing something?
With a finite range, you can bisect directly by splitting in the middle of the range. 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…
> 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]?