5 ms·

Interval arithmetic is what you're looking for, and there's an IEEE standard and many implementations.

crazygringo 6y ago
Thank you!! Yes, that turns out to be exactly it [1]. Looks like there's even at least one JavaScript library for it [2]. It seems like such a useful and intuitive idea I have to wonder why it isn't a primitive in any of the common programming languages. [1] https://en.wikipedia.org/wiki/Interval_arithmetic https://en.wikipedia.org/wiki/Interval_arithmetic [2] https://github.com/mauriciopoppe/interval-arithmetic https://github.com/mauriciopoppe/interval-arithmetic
- gugagore 6y ago
  Interval arithmetic certainly has its place. However, you don't find it used more often because a naive implementation results in intervals that are often uselessly huge. Consider x in [-1, 1], and y in [-1, 1]. x*y is also in [-1,1], and x-y in [-2, 2]. But now consider actually that y=x. That's consistent, but our intervals could be smaller than what we've computed.
  - crazygringo 6y ago
    Sure, but wouldn't realistic intervals be more like x in [0.29999999999999996, 0.30000000000000004]? I mean, intervals as large as whole numbers might make sense if your calculations are dealing with values in the trillions and beyond... but isn't the point of interval arithmetic to deal with the usually tiny errors that occur in FP representation?
- enriquto 6y ago
  > It seems like such a useful and intuitive idea I have to wonder why it isn't a primitive in any of the common programming languages. It is basically useless for numerical computation when you perform iterations. Even good convergent algorithms can diverge with interval arithmetic. As you accumulate operations on the same numbers, their intervals become larger and larger, growing eventually to infinity. It has some applications, but they are quite niche.
  - lifthrasiir 6y ago
    It is true that error intervals eventually go to infinity, but the very point is to keep them small enough to be useful throughout the calculation. IA is pretty bad for that but other approaches like affine arithmetic can be much better. (It still doesn't make an approachable interface for general programming languages though.)
  - crazygringo 6y ago
    But if the intervals are growing to infinity, then should you be trusting your result at all? Are there really cases where current FP arithmetic gives an accurate result, but where the error bounds of interval arithmetic would grow astronomically? It seems like you'd have to trust FP rounding to always cancel itself out in the long run instead of potentially accumulating more and more bias with each iteration. Is that the case? Wouldn't the "niche" case be the opposite -- that interval arithmetic is the general-purpose safe choice, while FP algorithms without it should be reserved for those which have been mathematically proven not to accumulate FP error? (And would ideally output their own bespoke, proven, interval?)
    - enriquto 6y ago
      > But if the intervals are growing to infinity, then should you be trusting your result at all? Most often, yes; the probability distribution of your number inside that interval is not uniform, it is most likely very concentrated around a specific number inside the interval, not necessarily its center. After a few million iterations, the probability of the correct number being close to the boundary of the interval is smaller than the probability of all your atoms suddenly rearranging themselves into an exact copy of Julius Caesar. According to the laws of physics, this probability is strictly larger than zero. Would you think it "unsafe" to ignore the likelihood of this event? I'm sure you wouldn't, yet it is certainly possible. Just like the correct number being near the boundaries of interval arithmetic. Meanwhile, the computation using classical floating point, typically produces a value that is effectively very close to the exact solution. > It seems like you'd have to trust FP rounding to always cancel itself out in the long run instead of potentially accumulating more and more bias with each iteration. Is that the case? The whole subject of numerical analysis deals with this very problem. It is extremely well known which kinds of algorithms can you trust and which are dangerous (the so-called ill-conditioned algorithms).
- yongjik 6y ago
  Currently, either a programmer understands that floating point numbers are complicated beasts, or they don't, and get surprised. With interval arithmetic, either a programmer would understand that floating point numbers are not actually numbers but intervals... or they wouldn't, and get surprised. So I don't really see much upside. If you know that you need interval arithmetic, chances are that you're already using it.
FabHK 6y ago
Another way to get a feeling for the error (simpler than fully fledged interval arithmetic) is to toggle the rounding rules from the usual (towards even, or so) to up and down, and observe the change in result. https://en.wikipedia.org/wiki/IEEE_754#Rounding_rules https://en.wikipedia.org/wiki/IEEE_754#Rounding_rules
PaulHoule 6y ago
That is overthinking it horribly. The problem is that the user wants to write 1/10 and 2/20 and 3/10 but those numbers aren't really in the binary system. The user gets some numbers (let's call them A, B and C) that aren't the same but they fool people at first because they not only deserialize as 0.1 but the they also serialize from 0.1. Trouble is that A + B != C but some other number. Excel tries to hide it but the real answer is to keep the exponent in base 10 if you plan to read and write numbers like 137.036 or 9.1E-31. How the mantissa is doesn't matter, it could be base 7 for all I care -- it is just an integer. Interval math is for much tougher problems like recursion of k * x * (1-x) is easily proven to have periodic orbits of infinitely long period, but if you are using 32-bit floats you can't have a period longer than 4 billion. That kind of qualitatively difference means that there's no scientific value in iterating that function with floats, although you can do accurate grid samples with interval arithmetic.

Thank you!! Yes, that turns out to be exactly it [1]. Looks like there's even at least one JavaScript library for it [2]. It seems like such a useful and intuitive idea I have to wonder why it isn't a primitive in any of the common programming languages. [1] https://en.wikipedia.org/wiki/Interval_arithmetic https://en.wikipedia.org/wiki/Interval_arithmetic [2] https://github.com/mauriciopoppe/interval-arithmetic https://github.com/mauriciopoppe/interval-arithmetic

gugagore 6y ago
Interval arithmetic certainly has its place. However, you don't find it used more often because a naive implementation results in intervals that are often uselessly huge. Consider x in [-1, 1], and y in [-1, 1]. x*y is also in [-1,1], and x-y in [-2, 2]. But now consider actually that y=x. That's consistent, but our intervals could be smaller than what we've computed.
- crazygringo 6y ago
  Sure, but wouldn't realistic intervals be more like x in [0.29999999999999996, 0.30000000000000004]? I mean, intervals as large as whole numbers might make sense if your calculations are dealing with values in the trillions and beyond... but isn't the point of interval arithmetic to deal with the usually tiny errors that occur in FP representation?
enriquto 6y ago
> It seems like such a useful and intuitive idea I have to wonder why it isn't a primitive in any of the common programming languages. It is basically useless for numerical computation when you perform iterations. Even good convergent algorithms can diverge with interval arithmetic. As you accumulate operations on the same numbers, their intervals become larger and larger, growing eventually to infinity. It has some applications, but they are quite niche.
- lifthrasiir 6y ago
  It is true that error intervals eventually go to infinity, but the very point is to keep them small enough to be useful throughout the calculation. IA is pretty bad for that but other approaches like affine arithmetic can be much better. (It still doesn't make an approachable interface for general programming languages though.)
- crazygringo 6y ago
  But if the intervals are growing to infinity, then should you be trusting your result at all? Are there really cases where current FP arithmetic gives an accurate result, but where the error bounds of interval arithmetic would grow astronomically? It seems like you'd have to trust FP rounding to always cancel itself out in the long run instead of potentially accumulating more and more bias with each iteration. Is that the case? Wouldn't the "niche" case be the opposite -- that interval arithmetic is the general-purpose safe choice, while FP algorithms without it should be reserved for those which have been mathematically proven not to accumulate FP error? (And would ideally output their own bespoke, proven, interval?)
  - enriquto 6y ago
    > But if the intervals are growing to infinity, then should you be trusting your result at all? Most often, yes; the probability distribution of your number inside that interval is not uniform, it is most likely very concentrated around a specific number inside the interval, not necessarily its center. After a few million iterations, the probability of the correct number being close to the boundary of the interval is smaller than the probability of all your atoms suddenly rearranging themselves into an exact copy of Julius Caesar. According to the laws of physics, this probability is strictly larger than zero. Would you think it "unsafe" to ignore the likelihood of this event? I'm sure you wouldn't, yet it is certainly possible. Just like the correct number being near the boundaries of interval arithmetic. Meanwhile, the computation using classical floating point, typically produces a value that is effectively very close to the exact solution. > It seems like you'd have to trust FP rounding to always cancel itself out in the long run instead of potentially accumulating more and more bias with each iteration. Is that the case? The whole subject of numerical analysis deals with this very problem. It is extremely well known which kinds of algorithms can you trust and which are dangerous (the so-called ill-conditioned algorithms).
yongjik 6y ago
Currently, either a programmer understands that floating point numbers are complicated beasts, or they don't, and get surprised. With interval arithmetic, either a programmer would understand that floating point numbers are not actually numbers but intervals... or they wouldn't, and get surprised. So I don't really see much upside. If you know that you need interval arithmetic, chances are that you're already using it.

FabHK 6y ago

Another way to get a feeling for the error (simpler than fully fledged interval arithmetic) is to toggle the rounding rules from the usual (towards even, or so) to up and down, and observe the change in result. https://en.wikipedia.org/wiki/IEEE_754#Rounding_rules https://en.wikipedia.org/wiki/IEEE_754#Rounding_rules

PaulHoule 6y ago

That is overthinking it horribly. The problem is that the user wants to write 1/10 and 2/20 and 3/10 but those numbers aren't really in the binary system. The user gets some numbers (let's call them A, B and C) that aren't the same but they fool people at first because they not only deserialize as 0.1 but the they also serialize from 0.1. Trouble is that A + B != C but some other number. Excel tries to hide it but the real answer is to keep the exponent in base 10 if you plan to read and write numbers like 137.036 or 9.1E-31. How the mantissa is doesn't matter, it could be base 7 for all I care -- it is just an integer. Interval math is for much tougher problems like recursion of k * x * (1-x) is easily proven to have periodic orbits of infinitely long period, but if you are using 32-bit floats you can't have a period longer than 4 billion. That kind of qualitatively difference means that there's no scientific value in iterating that function with floats, although you can do accurate grid samples with interval arithmetic.