5 ms·

> 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

> 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).
  - dataflow 6y ago
    I suggest adding an example to demonstrate this effect because I don't think it's necessarily obvious for someone who hasn't already seen it.
  - eithed 6y ago
    With large integers - no, ie: `Math.pow(2, 55)+1 === Math.pow(2, 55)` returning true
- dataflow 6y ago
  There was a time when I thought (like you) that everybody should be using interval arithmetic, but then I came across a counterexample that convinced me I was wrong. I don't remember the precise example, but maybe the following will do the same for you. Say x = 4.0 ± 1.0. What is x / x? It should be x / x = 1.0 ± 0.0, but interval arithmetic will give you [3/5, 5/3]. Notice the interval is objectively wrong, as the result cannot be anything other than 1.0. Now imagine what happens if you do this a few more iterations. Your interval will diverge to (0, +∞), becoming useless. The moral of the story (which may be more obvious in hindsight): interval arithmetic is a local operation; error analysis is a global operation. Naturally the former cannot substitute for the latter.
  - generalizations 6y ago
    Your example only proves your point if every instance of x is the same x, with the same objective value. i.e., what if x/x is actually (x=5.0)/(x=3.0) ?
    - dataflow 6y ago
      Then you're computing x/y and not x/x...
    - Dylan16807 6y ago
      x can't be two values at the same time. It's one instance, not a class. If you have "scope1.x/scope2.x" then they don't cancel out, but that's not "x/x" And if you save a value for later, and change x, then that value isn't x anymore. (I assume you're using = to state the value, not as an assignment operator.)
  - dragonwriter 6y ago
    > Say x = 4.0 ± 1.0. What is x / x? > It should be x / x = 1.0 ± 0.0, but interval arithmetic will give you [3/5, 5/3]. This is the “dependency problem” which is eliminated in many cases, and mitigated in others, by rewriting so identical (vs. merely in components) values appear only once; when you might need a numerical answer at one point (if possible) but to use the value in further computations, this can be done by storing and manipulating values symbolically and extracting numerical results as needed.
- seoaeu 6y ago
  This feels like the central limit theorem. Accumulating a bunch of random variables is going to produce a normal distribution, and a normal distribution has an infinite interval.
  - blake1 6y ago
    Yeah, but the standard deviation goes by sqrt(n) for many operations, and there is significant autocorrelation. Interval arithmetic will give you worst-case bounds, which will quickly get fantastically pessimistic. Numerical analysis was a field invented to give realistic error bounds.

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).
- dataflow 6y ago
  I suggest adding an example to demonstrate this effect because I don't think it's necessarily obvious for someone who hasn't already seen it.
- eithed 6y ago
  With large integers - no, ie: `Math.pow(2, 55)+1 === Math.pow(2, 55)` returning true
dataflow 6y ago
There was a time when I thought (like you) that everybody should be using interval arithmetic, but then I came across a counterexample that convinced me I was wrong. I don't remember the precise example, but maybe the following will do the same for you. Say x = 4.0 ± 1.0. What is x / x? It should be x / x = 1.0 ± 0.0, but interval arithmetic will give you [3/5, 5/3]. Notice the interval is objectively wrong, as the result cannot be anything other than 1.0. Now imagine what happens if you do this a few more iterations. Your interval will diverge to (0, +∞), becoming useless. The moral of the story (which may be more obvious in hindsight): interval arithmetic is a local operation; error analysis is a global operation. Naturally the former cannot substitute for the latter.
- generalizations 6y ago
  Your example only proves your point if every instance of x is the same x, with the same objective value. i.e., what if x/x is actually (x=5.0)/(x=3.0) ?
  - dataflow 6y ago
    Then you're computing x/y and not x/x...
  - Dylan16807 6y ago
    x can't be two values at the same time. It's one instance, not a class. If you have "scope1.x/scope2.x" then they don't cancel out, but that's not "x/x" And if you save a value for later, and change x, then that value isn't x anymore. (I assume you're using = to state the value, not as an assignment operator.)
- dragonwriter 6y ago
  > Say x = 4.0 ± 1.0. What is x / x? > It should be x / x = 1.0 ± 0.0, but interval arithmetic will give you [3/5, 5/3]. This is the “dependency problem” which is eliminated in many cases, and mitigated in others, by rewriting so identical (vs. merely in components) values appear only once; when you might need a numerical answer at one point (if possible) but to use the value in further computations, this can be done by storing and manipulating values symbolically and extracting numerical results as needed.
seoaeu 6y ago
This feels like the central limit theorem. Accumulating a bunch of random variables is going to produce a normal distribution, and a normal distribution has an infinite interval.
- blake1 6y ago
  Yeah, but the standard deviation goes by sqrt(n) for many operations, and there is significant autocorrelation. Interval arithmetic will give you worst-case bounds, which will quickly get fantastically pessimistic. Numerical analysis was a field invented to give realistic error bounds.