Author here. The table-maker's dilemma is a problem if you insist on correct rounding. However, interval arithmetic does not require correct rounding. It merely requires rigorous error bounds. It turns out that a lot of the time when people ask how to obtain correctly rounded results, they are actually asking the wrong question, and what they really need is just error bounds.
This is why Arb has a lot more functions than MPFR: it's extremely difficult to implement correctly rounded functions as required by MPFR; Arb's contract (returning an error bound) is far easier to satisfy and works just as well 99% of the time.
From a software development point of view, the problem with correct rounding is that it doesn't compose: given correctly rounded functions f and g and correctly rounded input x, f(g(x)) is not (in general) correctly rounded. In interval arithmetic, the corresponding composition law (the inclusion property) does hold; this means that you can compose arbitrarily complicated functions without thinking.
Thank you for the reply! This is interesting, I didn't realize this. Unfortunately I'm still not sure I fully grasp it though: if I say 1.001 is "correctly rounded", that is equivalent to saying it has error bounds of +/- 0.0005. I could say either of these and they would mean the same thing. So what does it mean when you say you an establish rigorous error bounds but you can't guarantee correct rounding? If you can decrease the error bounds (which it seems you can, given this is arbitrary-precision) then isn't that equivalent to being able to round with more digits (precision)?
This is really cool, thank you. I implemented John Gustafson's "unum" intervals (as well as his "posits", that work of mine is more well known); and boy were they a pain in the butt. I'm not really working on this anymore, but it's neat to see a different approach (which I suspect is simpler in many ways).
Comments
Author here. The table-maker's dilemma is a problem if you insist on correct rounding. However, interval arithmetic does not require correct rounding. It merely requires rigorous error bounds. It turns out that a lot of the time when people ask how to obtain correctly rounded results, they are actually asking the wrong question, and what they really need is just error bounds.
This is why Arb has a lot more functions than MPFR: it's extremely difficult to implement correctly rounded functions as required by MPFR; Arb's contract (returning an error bound) is far easier to satisfy and works just as well 99% of the time.
From a software development point of view, the problem with correct rounding is that it doesn't compose: given correctly rounded functions f and g and correctly rounded input x, f(g(x)) is not (in general) correctly rounded. In interval arithmetic, the corresponding composition law (the inclusion property) does hold; this means that you can compose arbitrarily complicated functions without thinking.
Thank you for the reply! This is interesting, I didn't realize this. Unfortunately I'm still not sure I fully grasp it though: if I say 1.001 is "correctly rounded", that is equivalent to saying it has error bounds of +/- 0.0005. I could say either of these and they would mean the same thing. So what does it mean when you say you an establish rigorous error bounds but you can't guarantee correct rounding? If you can decrease the error bounds (which it seems you can, given this is arbitrary-precision) then isn't that equivalent to being able to round with more digits (precision)?
This is really cool, thank you. I implemented John Gustafson's "unum" intervals (as well as his "posits", that work of mine is more well known); and boy were they a pain in the butt. I'm not really working on this anymore, but it's neat to see a different approach (which I suspect is simpler in many ways).