Show HN: I made a calculator that works over disjoint sets of intervals

136

ffouronnes3 about 7 hours ago 18 commentsRead Article on victorpoughon.github.io

DE version is available. Content is displayed in original English for accuracy.

I've been studying interval arithmetic for the past few weeks and it's a really interesting field because while there is a ton of super interesting research published over the past decades, it has never really gotten the recognition that it deserves, IMO.

One reason for this is that standard interval arithmetic has really poor handling of division by intervals containing zero. If you compute 1 / [-1, 2] in regular interval arithmetic, you get either [-∞, +∞], or you have to say that the operation is undefined. Both solutions are virtually useless. The real answer of course is [-∞, -1] U [0.5, +∞]: i.e. a union of two disjoint intervals.

This is useful because you can confidently exclude a non empty set of the real numbers ([-1, 0.5]) from the set of possible values that you can get by dividing 1 by a number between -1 and 2.

But this definition of interval division yields a value that is not an interval. This is a problem if you want to define a closed arithmetic system, where you can build and evaluate arbitrary expression over interval values.

(This behavior extends to any non continuous function like tan() for example, which is implemented in my project - not without difficulties!)

Well the obvious solution is to define your arithmetic over disjoint unions of intervals. This is the subject of a 2017 paper called "Interval Unions" by by Schichl, H., Domes, F., Montanher, T. and Kofler, K..

This open-source project I made implements interval union arithmetic in TypeScript in the form of a simple interactive calculator, so you can try it out for yourself! The underlying TypeScript library is dependency free and implements interval union arithmetic over IEEE 754 double precision floats (JS native number type) with outward rounding. This guarantees accuracy of interval results in the presence of rounding issue inherent to floating point.

⚡ Community Insights

Discussion Sentiment

100% Positive

Analyzed from 620 words in the discussion.

Discussion (18 Comments)Read Original on HackerNews

fouronnes3•about 7 hours ago

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].

[0] https://github.com/victorpoughon/not-so-float

[1] https://victorpoughon.github.io/bidicalc/

[2] https://news.ycombinator.com/item?id=46234734

LXforever•4 minutes ago

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.

iamwil•about 3 hours ago

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

memalign•about 3 hours ago

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

_Microft•about 3 hours ago

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.

adito•about 2 hours ago

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

fouronnes3•about 2 hours ago

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!

globular-toast•about 2 hours ago

I was also a bit confused by this. I thought the standard notation was round brackets, but maybe doesn't work well in ASCII?

meindnoch•14 minutes ago

  (0, 1)

Is this an twice-open interval or a 2D vector?

See, this is why Bourbaki introduced the ]0,1[ notation.

qbit42•about 1 hour ago

Round brackets are standard in the US but that notation is used in France and some other places.

JSR_FDED•about 1 hour ago

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?

ngruhn•about 1 hour ago

It can be used in static analysis or type checking. E.g.

    if (x >= 0) {
      x += 10
      if (x =< 9) {
        // unreachable 
      }
    }

By maintaining an interval of possible values of x, you can detect the unreachable branch, because the interval becomes empty:

    initial: [-oo, oo]
    x >= 0 : [0, oo]
    x += 10: [10, oo]
    x =< 9 : [10, 9] (empty)

nicolodev•about 1 hour ago

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 :)

teiferer•about 1 hour ago

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.

anematode•about 2 hours ago

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.

fouronnes3•about 1 hour ago

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!

petters•about 1 hour ago

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

boobsbr•about 1 hour ago

Neat.