How do you compute the midpoint of an interval? (2014) [pdf] • Hacker News Board

Re: How do you compute the midpoint of an interval? (2014) [pdf]

#11

Post by kevinventullo » Fri, Mar 29, 2019, 2:46 PM UTC

Sean1708 wrote: post #10

fhars wrote: post #5

Similar things are relevant for calculations with integers (like array indexes), if you haven‘t yet, read this classic post about it: https://ai.googleblog.com/2006/06/extra-extra-read-all-about... (reader mode makes it accessible on iPhones, why don‘t people test their layouts with common browsers?).

In C and C++ (where you don't have the >>> operator), you can do this: 6: mid = ((unsigned int)low + (unsigned int)high)) >> 1; Since you're casting to unsigned int anyway, can't you just use / 2?

Yeah, I believe those compile to the same thing for unsigned ints. You can confirm using godbolt.

Re: How do you compute the midpoint of an interval? (2014) [pdf]

#12

Post by thaumasiotes » Fri, Mar 29, 2019, 2:55 PM UTC

Someone wrote: post #6

jacobolus wrote: post #4

Summary: to compute (a + b) / 2 and get the best answer for arbitrary inputs, you want: 0 if a == –b ±realmax if a or b is ±∞ otherwise compute (a - a/2) + b/2 at higher precision, then round to the nearest float

”±realmax if a or b is ±∞” That, IMO, is debatable. NaN is an option, too (as it is for the case a=+∞, b=-∞, so one can argue ”0 if a == –b” needs tuning, too) Both choices break the property m(I) ∈ I , but that may be fine, as NaN doesn’t mean the midpoint isn’t in the interval, but just that one cannot tell where in the interval it lies.

Is a == -b true when a and b are +inf and -inf? That's not what I would have expected.

Re: How do you compute the midpoint of an interval? (2014) [pdf]

#13

Post by jacobolus » Fri, Mar 29, 2019, 5:11 PM UTC

thaumasiotes wrote: post #12

Someone wrote: post #6

Earlier quoted context omitted.

”±realmax if a or b is ±∞” That, IMO, is debatable. NaN is an option, too (as it is for the case a=+∞, b=-∞, so one can argue ”0 if a == –b” needs tuning, too) Both choices break the property m(I) ∈ I , but that may be fine, as NaN doesn’t mean the midpoint isn’t in the interval, but just that one cannot tell where in the interval it lies.

Is a == -b true when a and b are +inf and -inf? That's not what I would have expected.

You are asking if ∞ == ∞? Yes.

Re: How do you compute the midpoint of an interval? (2014) [pdf]

#14

Post by wutbrodo » Fri, Mar 29, 2019, 5:23 PM UTC

jacobolus wrote: post #13

thaumasiotes wrote: post #12

Earlier quoted context omitted.

Is a == -b true when a and b are +inf and -inf? That's not what I would have expected.

You are asking if ∞ == ∞? Yes.

It's been years since I got my math degree, but IIRC this isn't true. At least, it's not true in enough framings that you can assert it this plainly. Infinity isn't just another number, and just because the symbols are identical in either side of the equals signs doesn't mean the entities described are.

Re: How do you compute the midpoint of an interval? (2014) [pdf]

#15

Post by jacobolus » Fri, Mar 29, 2019, 5:27 PM UTC

wutbrodo wrote: post #14

jacobolus wrote: post #13

Earlier quoted context omitted.

You are asking if ∞ == ∞? Yes.

It's been years since I got my math degree, but IIRC this isn't true. At least, it's not true in enough framings that you can assert it this plainly. Infinity isn't just another number, and just because the symbols are identical in either side of the equals signs doesn't mean the entities described are.

We are talking about the floating point number format and the behavior of computer programming languages.

In “mathematics”, the meaning of the symbol ∞ depends on what number system we are talking about. In some contexts ∞ is not a “number”, but rather a shorthand for a statement about limits. In other contexts it is a number.

If you want to learn about the “affinely extended real numbers”, which is what floating point numbers more or less approximate, you can read https://en.wikipedia.org/wiki/Extended_real_number_line