[fdej]

For anyone wondering about the difference between endpoint-based interval arithmetic ([a,b]) and midpoint-radius ([m +/- r]) arithmetic (ball arithmetic): they are often interchangeable, but they have different tradeoffs. Roughly speaking, standard interval arithmetic is better for subdivision of space, while ball arithmetic is better for representing individual numbers.

A good technical introduction to ball arithmetic is this paper by Joris van der Hoeven: https://www.texmacs.org/joris/ball/ball.html

[boulos]

Great write up!

I’m amused by your subdivision of space note, given Figure 1 :). There are clearly some problems and transforms that are better on N-spheres (N-balls?) and others on rectangles / N-cubes. Do you have a deeper intuition for which? (The x^2 example was simple and cute).

Years ago [1], we applied interval arithmetic to tracing groups of rays (and compared to geometric bounding via planes/frustums). I’d be curious to think through an equivalent with your midpoint ball arithmetic, but I feel like it would “need” to be parameterized as a ball of origins (easy) and then something else for the cone of directions —- maybe theta/phi clusters or “cluster of points on the unit sphere” (but converting back and forth is more expensive than the gains).

[1] http://graphics.stanford.edu/~boulos/papers/ia.pdf

[klyrs]

Joris's paper discusses high-dimensional balls with various metrics (where the max-norm gives equality between the "ball" and "interval" concepts), but I skimmed your paper and it looks like you're doing only doing 1d. It isn't immediately obvious to me how one would perform computations on, say, 3-dimensional euclidean balls using your library. Is this something you've thought through (or was my skim too shallow)?

[dnautics]

maxnorm in 3-dimensions is not euclidean. It is however, a metric space (which is why they call them "balls"). Note that the following formula for vectors x and y over R is a valid metric (obeys triangle inequality) for _all_ n in _all_ dimensions, with n=2 being the usual euclidean metric:

    d(x, y) = |sum_i((x_i - y_i)^n)|^(1/n)

The maxnorm is the limit as n -> infinity, and is also a proper metric space. (the collection of these spaces are called Lp spaces)

Of course in one dimension, all of these Lp metrics are identical.

https://en.wikipedia.org/wiki/Lp_space

[fdej]

The library doesn't support this directly. What you can do for normed vector spaces over R (or C) is to use the number types of Arb for the coordinate vectors, implementing your own norm and metric functions for the vector space on top of this. It's fairly easy to do since Arb handles all rounding errors in the underlying real arithmetic.

[eternalban]

What's the history/provenance of ball arithmetic? Was this a new insight out of INRIA or a well known approach not previously implemented? All links seem to circle back to you and Joris van der Hoeven, and arb [in the 2018-present time line].

[fdej]

I think the name "ball arithmetic" is Joris's idea. I don't have a good reference at hand, but I believe the idea of using a centered form of intervals is as old as interval arithmetic itself. Ball arithmetic has been used quite a bit for complex interval arithmetic, where it sometimes offer better enclosures than rectangular intervals, and another nice point of ball arithmetic is that it generalizes to more general normed spaces. However, before Joris's and my own work, I think very few people realized how useful ball arithmetic is specifically for arbitrary-precision arithmetic.

[eternalban]

Thank you.

So that sent me chasing interval arithmetic's history -- https://en.wikipedia.org/wiki/Interval_arithmetic -- and that page is also silent as to where did it come from. But academic.ru has the (surprising to me) answer that none other than Archimedes (not a surprise) used it:

"Interval arithmetic is not a completely new phenomenon in mathematics; it has appeared several times under different names in the course of history.

For example Archimedes calculated lower and upper bounds 223/71 < π < 22/7 in the 3rd century BC. Actual calculations with intervals has neither been as popular as other numerical techniques, nor been completely forgotten."

https://en.academic.ru/dic.nsf/enwiki/1037936

[jkhdigital]

Kinda reminds me of the difference between arithmetic coding and asymmetric numeral systems

[blurred]

Arithmetic coding encodes into range, ANS into single natural number. BTW, JPEG XL on ANS just got standardized.