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.
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.
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?)
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).
`Math.pow(2, 55)+1 === Math.pow(2, 55)` returning true
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.
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.)
> 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.
But if, in your code, you've copied x to y (not by reference), then it seems that x / y would correctly be [3/5, 5/3]. This is a feature, not a bug.
In any case, since intervals are more likely to be more like ± 0.000000000000001 when dealing with basic common non-iterative calculations, it doesn't seem like a problem in practice even if the compiler/interpreter doesn't optimize it away?
You're moving the goalposts here. Those are HUGE if's. You went from something you could trivially implement in any language to something that requires a LOT of infrastructure and will severely limit your options.
How are you going to handle (x - z) / (x + z) when z = 0? How are you going to handle f(x) / g(x) when they turn out to compute the same value in different ways?
You go from "I need to change float to interval<float>, give me 15 minutes" to "I need a computer algebra system, let me figure out if I can embed Mathematica/SymPy/Maple/etc. into program so I can do math." And even when you do that you STILL won't be able to handle cases where the symbolic engine can't simplify it for you. Which in general it won't be able to do.
> But if, in your code, you've copied x to y (not by reference), then it seems that x / y would correctly be [3/5, 5/3]. This is a feature, not a bug.
No, that is most definitely a bug. The correct result is 1.0, but you're producing [3/5, 5/3]. If that's not a bug to you then you might as well just output (-∞, +∞) everywhere and call it a day. You can insist on calling it a "feature" if it makes you feel better, but that won't change the fact that it's still just as useless (if not actively harmful) for your intended calculation as it was before.
Contrast this with just leaving it as a float instead of an interval, where you would've gotten the correct answer.
> In any case, since intervals are more likely to be more like ± 0.000000000000001, it doesn't seem like a problem in practice even if the compiler/interpreter doesn't optimize it away?
That's only after 1 iteration. Notice that in my example the error was multiplicative, not additive. Run more iterations and your error will magnify.
But there's nothing "wrong" about it, it's correct -- that's how it's designed to work. If you're starting with non-extreme values and just miniscule floating-point errors and iterate 1,000 times with basic arithmetic I still don't see how it's going to cause a problem. E.g.:
Math.pow((1 + Number.EPSILON), 1000) => 1.000000000000222
If you're multiplying a million or billion times then that's where I can now understand you should be an expert an numerical analysis in the first place to have any confidence in your result, and you know whether or not your float result can be trusted or not at all.
But the good thing is that if you don't know what you're doing, started with interval arithmetic and it ballooned to (-∞, +∞), then that's a strong signal you shouldn't necessarily be trusting the algorithm's results at all, and to go talk to someone with a background in numerical analysis, right?
Whereas if you iterate a million times and the interval is still miniscule compared to your values, you have absolute confidence you're fine. Seems useful to me -- not useless or actively harmful at all.
> Contrast this with just leaving it as a float instead of an interval, where you would've gotten the correct answer.
But if I type into my console:
var a = 0.1; var b = a + 0.2; b -= 0.2; b == a;
Heck, to use your own division example:
(0.1 + 0.2 - 0.2) / 0.1 ==> 1.0000000000000002
Anyways, thanks for trying to explain.
(0.1 + 0.2 - 0.2) / 0.1 ==[+/- .001] 1.0 => True
Now you've got me learning about how affine arithmetic can help with the dependency problem but has its own drawbacks. Thanks for pointing me in that direction!
Even if this may come out as a bit snarky, this is a very good, honest, and helpful answer. At least, it would be helpful to extremely skeptical people like me. I'm a bit like crazygringo, and I cannot be convinced of anything until I have tried it myself and dirtied my hands with it.
To crazygringo: for a concrete, real-world example, try to implement a Kalman filter (a very simple numerical algorithm) using interval arithmetic. It simply doesn't work. You'll see that you cannot extract any useful result from the output of the computation. The implementation of an "interval Kalman filtering" is a (niche) subject of current research, where various very complicated algorithms are being invented to try to reproduce the nice properties of Kalman filtering--even when using something obviously inappropriate like interval arithmetic. For an intuitive understanding, assume that the input data are quantized to integer values, so that the starting intervals are of length 1.
Numerical analysis was a field invented to give realistic error bounds.
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.
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.
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?