Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

victorpoughon.github.io

Post reply on HN
Print view View original

41–50 of 61 posts

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

#41

Post by lou1306 »

Sorry to be a party pooper, the Web app is neat, but I have some reservations about the paper.

Namely, the "powerset of intervals" domain has been known since the '70s [1], and powerset domains have been generalised to arbitrary base domains decades ago [2]. A paper from the mid-2010s on these topics that lacks any engagement with the abstract interpretation literature is a bit disappointing.

As for the interpretation of division suggested here, it makes, say, 1 / S non-distinguishable from 1 / ([0, 0] U S) for any set of intervals S, which sounds suspicious.

[1] Patrick Cousot and Radhia Cousot. 1979. Systematic Design of Program Analysis Frameworks. In 6th ACM Symposium on Principles of Programming Languages (POPL), January 1979. ACM Press, San Antonio, TX, USA, 269–282. https://doi.org/10.1145/567752.567778

[2] Gilberto Filé and Francesco Ranzato. 1999. The Powerset Operator on Abstract Interpretations. Theor. Comput. Sci. 222, 1–2 (1999), 77–111. https://doi.org/10.1016/S0304-3975(98)00007-3

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

#42

Post by lou1306 »

SkiFire13 wrote: post #38

Expanding the logic to union of intervals looks cool, but what is the complexity of that? Since you introduce the the possibility of an operation on an interval producing two intervals I suspect executing N operations might have an exponential complexity, which unfortunately makes this unfeasible to use for some common intervals applciations like abstract interpretation, unless you start introducing approximations on…

Yes, this is well-known (eg. in abstract interpretation). As you said, usually you can set a "cap" to the size of these objects, and start merging intervals when you hit the cap. But at least in abstract interpretation it seems that they simply consider more sophisticated domains than intervals.

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

#43

Post by noncovalence »

fouronnes3 wrote: post #2

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…

Very cool, I'll definitely be playing around with this some more! Two questions:

- How difficult would it be to add many-valued functions to this? It would be really nice to be able to get the full set of [pi/2, pi/2] + n[2pi, 2pi] from asin(1) without needing to break out Mathematica.

- And:

> Numbers input by the user are interpreted as the smallest interval that contains the IEEE 754 value closest to the input decimal representation but where neither bounds are equal to it

Am I missing something obvious, or should this be the other way round, i.e. the output bounds are the closest two IEEE 754 numbers that contain the input number?

The way it's written I'd interpret the smallest interval to be IEEE754(input)+[-epsilon, epsilon] for infinitesimally small epsilon.

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

#46

Post by zamadatix »

mbo wrote: post #39

Could this support a native datetime type? I shipped a much worse of this for managing repeated events and schedules.

Naively, what breaks by doing datetime -> epoch -> interval -> datetime over some other form of implementation?

I tend to avoid datetimes as much as working with printers because the answer is always "more annoying than you'd first think" :D.

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

#47

Post by fouronnes3 »

wvlia5 wrote: post #45

Hey, what about this idea? redefine interval representation, such that [a, b] means the same if a<b; but if b<a, it means [-∞, b]U[a, +∞]. Then your example would become 1/[-1,2]=[0.5,-1]

That's a very cool idea :) It was proposed as far back as 1968 (!) in a paper by none other than the legend of floating point himself: Wiliam Kahan https://interval.louisiana.edu/historical-preprints/1968-Kah...

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

#50

Post by roger_ »

I can see valid uses of this but I also feel like a probabilistic calculator would be more useful.

e.g. the result for the 1 / [-1, 2] example doesn’t tell you how likely each value is and it clearly won’t be uniformly distributed (assuming the inputs are).

Post reply on HN