I recently implemented something somewhat similar, but from the perspective of set membership.
I therefore needed to include a complement operation, so that I could do full Boolean analysis of interval membership.
Your intervals are all closed sets, consequently the complements are open intervals. I chose not to distinguish between open and closed intervals, since for my practical purposes whether the end points are members of the set is unimportant.
Of course, with inexact arithmetic, the question of whether the set is open of closed probably not well-defined.
Author here. Outward rounding to combat precision issues is what interval arithmetic is most known for (try 0.1+0.2 with "full precision mode" enabled), but that's really a shame in my opinion. Outward rounding is cool, but the "inclusion property", as it's known in research papers, works at every scale! This is what enables things like:
50 * (10 + [-1, 1])
[450, 550]
which is lovely, I think. Adding the union layer to it enables even cooler things, like the true inverse of the square function. Did you know it's not sqrt? Try 'sqinv(64)'.
I made interval calculator actually mostly as a way to test my implementation of interval union arithmetic [0], which I needed for another project: a backwards updating spreadsheet [1][2].
Nice! I am interested in how the arithmetic you implemented differs from the IEEE 1788 Standard for Interval Arithmetic (and how the two linked papers relate to it). To address the challenges you mention, did you have to start from scratch or was it something that can build on top of the IEEE standard?
Interesting! I'm not familiar with IEEE 1788. The TypeScript library (not-so-float) that I wrote which powers the calculator uses the JS Number type which is double precision IEEE 754. Outward rounding is not supported by JS so I used a bit level manipulation hack by casting to TypedArray [0] to implement the equivalent of C's nextafter() function. Otherwise I mostly followed Hickey & van Emden paper which is really delightful [1]. The real hard work is actually generating all the test cases. Good luck getting 100% test coverage on interval division!
Very nice, thanks for sharing!
Maybe show which upper or lower values are included in the intervals?
A notation I am familiar with uses outward facing brackets if the value is not included in the interval. That always applies to infinity.
Applied to the cases here:
]-∞, -1] U [0.5, +∞[
The excluded interval in between becomes ]-1, 0.5[ then.
That’s how min (and analogously max) works, right?
min(A, B) = [lo(A,B), lo (hi(A), hi(B))].
Edit: idea: copy a formula from the results section to the input field if the user clicks/taps on it.
From reading the linked paper[0], It explains closed interval only. "An interval union is a set of closed and disjoint intervals where the bounds of the extreme interval can be ±∞".
It's possible to support that but it makes the code very very much more complicated. I've decided early on to not support it. Would be a cool addition though!
Very cool! I don't entirely understand some of the operations, but for what I do understand its pretty neat.
I wish in classes we were introduced to a notion of arithmetic on intervals as it comes up. Like in basic statistics with confidence intervals there's ±, as well as in the quadratic equation. It found some what dissatisfying we couldn't chain the resulting a series of operations and instead repeat the operations for the 2 seperate values of the ±. I get a teacher would rather not get hung up on this because they want to bring it back to the application generally, like solving a more complicated equation or hypothesis testing in basic stats. I just wish they hinted at the idea we can do arithmetic on these kinds of things more generally.
I realise what you've got here is well beyond this, but seeing this was some level of validation that treating the interval as a piece of data with its own behaviour of certain operations does make some sense.
Very nice work. I was wondering if it might be useful to combine this with a library for arbitrary precision arithmetic. How difficult do you think that might be?
Thanks! Arbitrary precision arithmetic is definitely something I'd like to learn more about, yeah. Haven't had time to study it so much yet unfortunately.
Excellent!! I love interval arithmetic and also wrote a TS implementation for a graphing calculator project. Agree that it's very underrated, and I wish that directed rounding was exposed in more languages.
Yeah it's super interesting. Like you said, I learned that the IEEE 754 spec actually requires that complete implementations of floating point numbers expose a way to programmatically choose the rounding mode. As far as I know only C allows you to do that, and even then it depends on hardware support. For JS I had to use ugly typedarray casts. Which kinda only accidentally work due to endianess. But technically there should be an API for it!
There's other unused stuff in IEEE 754 like that: the inexact bit or signaling NaNs!
I just read up on interval arithmetic. I understand its desirable properties. Where in practice have you applied it? What’s a real world application for interval arithmetic?
I’m working on a static analyser at the moment that does this, and the inferences that can be made just from the information of intervals is quite impressive.
One thing you run into pretty quickly though in a lot of languages is integer overflow ruining your day - in your example above the commented section is reachable for signed ints that support overflow and that adds a whole other layer of complexity to things.
In physics, whenever you make a measurement it has a precision. Usually you represent this as a normal distribution, but for calculations it can be easier to represent this as an interval.
The police measure the distance my car travelled [ 99.9, 100.1 ] m and the time it took [ 3.3, 3.4 ] s - how fast was my car going? [29.38, 30.33] m/s according to the interval calculator.
Physics students learn exactly this method before they move on to more sophisticated analysis with error distributions.
It’s astonishing how nobody hasn’t mentioned abstract interpretation yet. Under classical static analysis, if you can “prove” that a variable does not have values in some unsound zones, you can e.g. “prove” soundness or apply further optimizations.
The interval abstract domain works under interval analysis with an algebra that’s the same of this calculator. It’s funny to implement something like that on source/binary level :)
You could add a feature where it will compute the global optimum of any function of a small number of variables. Branch and bound with interval arithmetic works well for a small number of variables.
Disjoint unions of intervals seems like a nice thing to have
Very cool. This feels like one of those ideas that makes interval arithmetic go from “interesting but frustrating” to actually useful.
I’d be curious how you handle the growth in the number of disjoint intervals over repeated operations, since that seems like the practical bottleneck.
I don't handle it, ahah. You are right that if you take any classical numerical computing algorithm and replace the floating point reals by interval unions, most of the time the number of intervals in the unions in each of your variables will grow very fast. This is one of the problems of unions and as far as I'm aware it's a topic of active academic research.
I recently implemented something somewhat similar, but from the perspective of set membership.
I therefore needed to include a complement operation, so that I could do full Boolean analysis of interval membership.
Your intervals are all closed sets, consequently the complements are open intervals. I chose not to distinguish between open and closed intervals, since for my practical purposes whether the end points are members of the set is unimportant.
Of course, with inexact arithmetic, the question of whether the set is open of closed probably not well-defined.
Author here. Outward rounding to combat precision issues is what interval arithmetic is most known for (try 0.1+0.2 with "full precision mode" enabled), but that's really a shame in my opinion. Outward rounding is cool, but the "inclusion property", as it's known in research papers, works at every scale! This is what enables things like:
which is lovely, I think. Adding the union layer to it enables even cooler things, like the true inverse of the square function. Did you know it's not sqrt? Try 'sqinv(64)'.I made interval calculator actually mostly as a way to test my implementation of interval union arithmetic [0], which I needed for another project: a backwards updating spreadsheet [1][2].
[0] https://github.com/victorpoughon/not-so-float
[1] https://victorpoughon.github.io/bidicalc/
[2] https://news.ycombinator.com/item?id=46234734
Nice! I am interested in how the arithmetic you implemented differs from the IEEE 1788 Standard for Interval Arithmetic (and how the two linked papers relate to it). To address the challenges you mention, did you have to start from scratch or was it something that can build on top of the IEEE standard?
Interesting! I'm not familiar with IEEE 1788. The TypeScript library (not-so-float) that I wrote which powers the calculator uses the JS Number type which is double precision IEEE 754. Outward rounding is not supported by JS so I used a bit level manipulation hack by casting to TypedArray [0] to implement the equivalent of C's nextafter() function. Otherwise I mostly followed Hickey & van Emden paper which is really delightful [1]. The real hard work is actually generating all the test cases. Good luck getting 100% test coverage on interval division!
[0] https://github.com/victorpoughon/not-so-float/blob/main/src/...
[1] https://fab.cba.mit.edu/classes/S62.12/docs/Hickey_interval....
This is great. You might be interested in Matt Keeter's work on Implicit surfaces, and using interval math for its optimization:
https://youtu.be/UxGxsGnbyJ4?si=Oo6Lmc4ACaSr5Dk6&t=1006
You might be interested in this graphing calculator I made using interval arithmetic:
https://memalign.github.io/m/formulagraph/index.html
Some detail on how this works, including links to the relevant interval math code:
https://memalign.github.io/p/formulagraph.html
Very nice, thanks for sharing! Maybe show which upper or lower values are included in the intervals? A notation I am familiar with uses outward facing brackets if the value is not included in the interval. That always applies to infinity.
Applied to the cases here:
]-∞, -1] U [0.5, +∞[
The excluded interval in between becomes ]-1, 0.5[ then.
That’s how min (and analogously max) works, right? min(A, B) = [lo(A,B), lo (hi(A), hi(B))].
Edit: idea: copy a formula from the results section to the input field if the user clicks/taps on it.
From reading the linked paper[0], It explains closed interval only. "An interval union is a set of closed and disjoint intervals where the bounds of the extreme interval can be ±∞".
[0]: https://www.ime.usp.br/~montanhe/unions.pdf
It's possible to support that but it makes the code very very much more complicated. I've decided early on to not support it. Would be a cool addition though!
I was also a bit confused by this. I thought the standard notation was round brackets, but maybe doesn't work well in ASCII?
Round brackets are standard in the US but that notation is used in France and some other places.
See, this is why Bourbaki introduced the ]0,1[ notation.
Very cool! I don't entirely understand some of the operations, but for what I do understand its pretty neat.
I wish in classes we were introduced to a notion of arithmetic on intervals as it comes up. Like in basic statistics with confidence intervals there's ±, as well as in the quadratic equation. It found some what dissatisfying we couldn't chain the resulting a series of operations and instead repeat the operations for the 2 seperate values of the ±. I get a teacher would rather not get hung up on this because they want to bring it back to the application generally, like solving a more complicated equation or hypothesis testing in basic stats. I just wish they hinted at the idea we can do arithmetic on these kinds of things more generally.
I realise what you've got here is well beyond this, but seeing this was some level of validation that treating the interval as a piece of data with its own behaviour of certain operations does make some sense.
Very nice work. I was wondering if it might be useful to combine this with a library for arbitrary precision arithmetic. How difficult do you think that might be?
Thanks! Arbitrary precision arithmetic is definitely something I'd like to learn more about, yeah. Haven't had time to study it so much yet unfortunately.
Why not use disks / exterior disks in the complex numbers plane instead of intervals ? It might make the mental model easier to reason about
Excellent!! I love interval arithmetic and also wrote a TS implementation for a graphing calculator project. Agree that it's very underrated, and I wish that directed rounding was exposed in more languages.
Yeah it's super interesting. Like you said, I learned that the IEEE 754 spec actually requires that complete implementations of floating point numbers expose a way to programmatically choose the rounding mode. As far as I know only C allows you to do that, and even then it depends on hardware support. For JS I had to use ugly typedarray casts. Which kinda only accidentally work due to endianess. But technically there should be an API for it!
There's other unused stuff in IEEE 754 like that: the inexact bit or signaling NaNs!
I just read up on interval arithmetic. I understand its desirable properties. Where in practice have you applied it? What’s a real world application for interval arithmetic?
It can be used in static analysis or type checking. E.g.
By maintaining an interval of possible values of x, you can detect the unreachable branch, because the interval becomes empty:I’m working on a static analyser at the moment that does this, and the inferences that can be made just from the information of intervals is quite impressive. One thing you run into pretty quickly though in a lot of languages is integer overflow ruining your day - in your example above the commented section is reachable for signed ints that support overflow and that adds a whole other layer of complexity to things.
We recently implemented this idea in an LLVM optimisation pass based on value-range information from sensor datasheets [1].
[1]: https://dl.acm.org/doi/pdf/10.1145/3640537.3641576
In physics, whenever you make a measurement it has a precision. Usually you represent this as a normal distribution, but for calculations it can be easier to represent this as an interval.
The police measure the distance my car travelled [ 99.9, 100.1 ] m and the time it took [ 3.3, 3.4 ] s - how fast was my car going? [29.38, 30.33] m/s according to the interval calculator.
Physics students learn exactly this method before they move on to more sophisticated analysis with error distributions.
And one might want to approximate error distribution calculus with a method that will look like the one here
It’s astonishing how nobody hasn’t mentioned abstract interpretation yet. Under classical static analysis, if you can “prove” that a variable does not have values in some unsound zones, you can e.g. “prove” soundness or apply further optimizations.
The interval abstract domain works under interval analysis with an algebra that’s the same of this calculator. It’s funny to implement something like that on source/binary level :)
The last point in your intro description can't be stressed enough: this allows for safe handling of rounding errors in floating point operations.
Though you are inherently losing precision: there are values in the output interval which don't have a corresponding input that causes this output.
Interals can be used to model errors and uncertainty and this lets you see how they conpound in calculations like speed = distance over time.
You could add a feature where it will compute the global optimum of any function of a small number of variables. Branch and bound with interval arithmetic works well for a small number of variables.
Disjoint unions of intervals seems like a nice thing to have
Neat.
Very cool. This feels like one of those ideas that makes interval arithmetic go from “interesting but frustrating” to actually useful. I’d be curious how you handle the growth in the number of disjoint intervals over repeated operations, since that seems like the practical bottleneck.
I don't handle it, ahah. You are right that if you take any classical numerical computing algorithm and replace the floating point reals by interval unions, most of the time the number of intervals in the unions in each of your variables will grow very fast. This is one of the problems of unions and as far as I'm aware it's a topic of active academic research.