Toward an API for the Real Numbers
blog.acolyer.org
blog.acolyer.org
Exact Reals are an interesting topic. They go beyond fractions and and algebraic numbers by representing numbers as some kind of object that supports querying an arbitrary number of digits. This object may be a stream, generator, or function. There is some similarity between its implementation techniques and those of automatic differentiation. The theory behind exact reals goes quite deep.
Some other interesting things to look at: - https://hackage.haskell.org/package/exact-real - https://www.youtube.com/watch?v=h7g4SxKIE7U - https://github.com/dpsanders/ExactReals.jl
Also the creator of the rope data structure for storing and efficiently mutating large strings (used by many text editors); as well as the c memory model.
Edit: the paper claims that you need exact equality tests to avoid printing unnecessary zeros at the end of decimal expansions, among other things.
Interesting that this work was done by Hans-J. Boehm, better known for the widely used Boehm garbage collector.
Proof: 1) suppose you can decide whether "x<y" for all x,y. 2) Then, for all x,y you can decide whether x==y because that's just "!(x<y) && !(y<x)"
Then you have a scientist reading this, wants it for research and then wonders why a simple 3 lines in Python code takes 3 days to complete. True story!
I keep wondering and never have this answered to my satisfaction: if so many people are just using floating point numbers in scientific calculations, and arguably even most scientists don't understand FP math any way better than the users of Android's Calculator app, then how many bad results are out there, that could be attributed to FP errors?
Related: I don't understand why the default in scientific computing isn't some kind of scheme with error band propagation. What I mean is, when dealing with measurements, the result of 2.1 * 2.12345 isn't 4.459245, because the result exceeds the precision of the first factor. I'd like a common API that handles this, whether implicitly (through notation) or explicitly (through requiring you to state the precision of every number you use).
What you want would maybe be better as probability distributions (maybe parameterized with rational numbers)
It's poor because it's undecidable. We would ideally want to work with the real numbers, but no computational model can represent all real numbers (by a trivial cardinality argument).
Obviously, we can make useful progress in practice and evolve beyond the floating point representation (at least for general tasks), similar to what we did for other theoretically undecidable problems (like garbage collectors), but let's not pretend it's something that's easy to fix.
The paper is interesting and talks about very real problems, but it's still a far cry from something that can be used in production.
https://mathoverflow.net/questions/40618/uncomputability-of-...
Likewise, equality of functions is also undecidable, but you never see people bringing that up in the context of Higher Order Functions.
Although computable reals have many properties shared by the actual real numbers (e.g. they are a field, which is not that trivial of a property), they are also different in very significant ways, for example, they aren't computably comparable, they aren't computably enumerable, their order is not computable.
Also, real analysis works very differently on that set, for example, it is not guaranteed that the least upper bound of a bounded increasing sequence of elements of the computable reals is itself a computable real.
Even ignoring feasibility in practice, working with non-standard mathematical structures is very unintuitive, much more than floating point numbers can be. (Let alone reasoning about the time-complexity of operations in that setting!)
Real Java programs produce numbers via arithmetic and finite applications of java.lang.Math functions. Those are the numbers that this API hopes to handle.
The issue isn't writing Java methods that do stuff, the issue is writing Java methods that expose an API that can be reasonably used to model a real-world problem that uses real numbers.
I'm not saying it can't be done. Much in the same way as writing a garbage collector is theoretically an undecidable problem and yet we have no lack of garbage collectors around, I expect research in this topic to move forward and eventually produce algorithms and methods that can be put in production software.
The point I'm trying to make is that (yet again, pretty much like garbage collectors) you are serving multiple masters here. We want the API to be a reasonable approximation to the actual real arithmetic, while at the same time being efficient enough that it's usable in practice, while at the same time being intuitive enough to match people's expectation of how real numbers 'should' work.
Again, we already have a solution to that problem. It's called 'using floating points'. The case being made is that 'using floating points' is hard and prone to error, because it satisfies requirements (1) and (2) but fails spectacularly at (3).
Of course people with (relatively) sophisticated math knowledge are going to be able to work it out no matter what, the same way people are able to work with floating points right now, and very efficiently so. We all took Numerical Analysis in college. The issue is that the kind of problems raised by using floating points are hard to think about, require very specific knowledge, and cause bugs that are hard to even detect.
Because a model that considers all computable real numbers would be similarly unintuitive, we should restrict ourselves to a smaller set that works in a more intuitive way. How should that set work is a HARD problem.
I'd argue that we actually have a pretty good answer: decimal floating point satisfies all three of your requirements.
It’s used in production in the default Android calculator app. Does that not count?
But an API for a language like Java needs more generality than that. The use case was (relatively) simple, (relatively) predictable, and (relatively) self-contained.
Crucially, equality in general is still undecidable (it wouldn't play nice with Collections), and it's not obvious that numerical algorithms would in general play nice with it. I'm also not really convinced that having random functions that could either terminate or not in your API is really more intuitive than floating points, but de gustibus non disputandum est.
There's also the issue of performance in non-toy examples. With the world going more and more the route of ML, efficiency of numerical algorithms is not a secondary concern.
Perhaps. Some algorithms in numerical analysis are only "backwards stable" as opposed to forwards stable. This includes all possible algorithms for things like Singular Value Decomposition. See: https://mathoverflow.net/questions/369930/why-is-uncomputabi...
> With the world going more and more the route of ML, efficiency of numerical algorithms is not a secondary concern.
ML is going in the direction of very low precision floating point numbers, like 16 bit floats. High precision doesn't seem to matter there.
No computational model can represent all integers, either, by a simple "number of atoms in the universe" argument.
Cantor isn't the problem here.
----
Separately, I'm almost certain that exact real arithmetic is being used in Houdini to do boolean intersections. That's as "production" as you can get.
It's relatively easy to make a model that works essentially the same as the actual integers (most modern programming languages have a built-in or stdlib variant of bignum), while it's prohibitively difficult to do the same with real numbers. And yes, computability is in fact the difference here, because as long as you are able to keep up the illusion of infinite memory, the integer version problem is trivial, but the real version stays just as hard.
-- edit answering the edit: I'm not familiar with that application, but if I'm not mistaken graphical software uses a different model than the one outlined in the OP, based on algebraic approximations. I'm not saying this stuff doesn't exist, obviously. I was talking about the general rationale behind the OP, i.e. using a model like this one instead of floating point computation for generic software.
For real numbers, we can come up with precise representations as well. Basically ASTs of permitted operations like addition, root of this polynomial, integral of this function, etc. If your set of permitted operations is large enough, you can represent any number that human language can encode. But operations on those representations are non-trivial.
Basically, for reals there is no representational space which is easy for "powerful" operations to navigate. For integers, there is the n-ary representation. But even that representation makes some operations non-trivial. What is the next larger prime number? What are a given integer's prime factors? Switching the representation to represent integers through their prime factors makes answering that question easier, but then suddenly other questions become non-trivial like addition of two numbers.
None of the two issues has anything to do with cantor.
This is a fallacy. The standard model for Computable Real Analysis, Type Two Effectivity, supports computation over all real numbers. See: https://en.wikipedia.org/wiki/Computable_analysis#Real_numbe...
Essentially, in TTE, a real number is an arbitrary stream of digits that can come from any source. Therefore any real number can be computed on.
Additionally, the ability to decide equality of floating point numbers is an illusion. Rounding errors can make numbers that ought to equal each other not equal each other.
I agree with your points about this problem being difficult. But the cardinality argument is neither here nor there. The cardinality argument is based on classical logic, and has no relevance to computation.
In constructive mathematics it is perfectly possible that all real numbers can be represented by finite algorithms. And even that all functions defined on all the reals are continous: a finite constraint of the output can be computed from a finite constraint on the input.
But, starting from a definition of the reals as a Cauchy sequence we have a long way to go to get something which can be practically computed on. I think RealPCF [0] was a step in the right direction.
All I'm saying with the cardinality argument is that because real numbers are fundamentally unlike integers, obvious methods of doing things won't work, and we are stuck (at least for the time being) with leaky abstractions.
I make no claim about the existence of better/more intuitive solutions. My only counterpoint is that while the ideas outlined in the paper are certainly valuable, I don't think the framework is mature enough to replace the default representation for real numbers in a programming language like Java, at least not without further work and/or proof that it can be adapted to a more general setting without disastrous performance decay.
> But, starting from a definition of the reals as a Cauchy sequence...
I trust that what you're saying is true, but I'm not familiar with that topic, I'm sorry. Thanks for sharing the paper.
It’s pretty important to define what you mean by “error”. We should not conflate state or execution errors with approximation errors, they are very very different kinds of errors. It is quite often not an error condition to have an approximation, and so would not count as a “leak”.
> If it only takes 6k lines to provide an API for more precise real numbers, then almost every programming language should have it.
There are a lot of libraries in a lot of languages for supporting arbitrary precision, big numbers, and other various representations. I’d venture to say that almost every programming language does have it, if you count a third party or open source library as having it.
On the other hand, high precision reals is a performance drain of enormous magnitude if you don’t always need it. Do keep in mind that even with all their problems, 32 bit floats and 64 bit doubles are really fast compared to software number libraries, the IEEE formats have broad hardware support that doesn’t exist for high precision reals.
Arbitrary precision is very different from exact real arithmetic.
And I’m curious whether you meant that exact real arithmetic is different in such a way that it would change either of the points that I made? Does it mean that performance is good enough that all languages should have it built in? Does it mean that approximation errors should then be considered the same as execution errors?
Some languages give exceptions here, unless specially told not to.
Wolfram alpha has that as exactly equal to
1/(3pi - 18)
Edit: (Or use 0.15708 instead of 9 in your link.)
https://github.com/microsoft/calculator/blob/master/src/Calc...
There are also the irrationals, and most of those cannot even be expressed (fortunately, since they cannot be expressed, there's no chance of you bumping into them by accident - so it's somewhat of a moot point).
The subset that you want to aim for is not the rationals, but the definable reals: https://en.wikipedia.org/wiki/Definable_real_number.
"We solved this 40 years ago in SmallTalk!"
That is, both have the surprise for most people that (/ 1 3) doesn't get rounded or truncated by default, due to the default of supporting rationals. You have to coerce into a floating point, right? Couldn't you do the same with exact reals? Put them at the top of the tower and maintain existing projections through the tower?
Edit:. Note that I don't think this precludes the algorithms here. Just that a type system that could use the tower could be augmented to get here. If that makes sense. Hence why I would think it would be mentioned. It is the expectations that things project in one direction that folks want? Right?
edit: now that I think about it, that would require some really nice optional chaining syntax to be even slightly usable.
My understanding is that in IEEE 754 compliant implementations of floating-point arithmetic, commutativity over "+" holds but not associativity. (With the possible exception to commutativity for the NaNs, though I don't remember offhand whether this caveat is necessary).
Most people who complain really just want a rational number type.