Hacker News new | past | comments | ask | show | jobs | submit login

> the ability to define the kind of numbers you want to be working with and their precision is fairly poor in computer science...

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.




> but no computational model can represent all real numbers (by a trivial cardinality argument)

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.


By the same token computers are finite state machines? Yes, technically they are, but it's not really useful to conceptualise them this way.

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.


The issue is one of representation and algorithms. For integers, you can provide a simple representation together with simple algorithms for addition, subtraction, multiplication, division with modulo, printing in decimal form, comparison which one is larger, etc.

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.


> no computational model can represent all real numbers (by a trivial cardinality argument).

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.

[0]: https://www.cs.bham.ac.uk/~mhe/papers/realpcf.pdf


Again, I don't disagree with any of this. The argument advanced by the OP is that floating point numbers are not intuitive to use for the general public because they don't work like the unique complete ordered field up to isomorphism.

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.


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

It’s used in production in the default Android calculator app. Does that not count?


It does count, and it's certainly "points" for the ideas there (not that the author needs my validation...)

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.


> it's not obvious that numerical algorithms would in general play nice with it

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.


Surely working with computable reals is sufficient? There's no point in writing a computer program that attempts to work with non-computable reals, for obvious reasons. And computable reals are countable.


It certainly is. The point is, is it necessary? (To be really pedantic one could ask which computable reals, but let's assume the usual definition, i.e. the set of reals defined by a computable Dedekind cut.)

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


That may be a valid theoretical objection, but Java does not have a "least upper bound" function, so its computability is not of practical interest to designing a real number Java API.

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.


It does have Double::compare though, doesn't it?

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.


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


Equality of computable reals is undecidable.

https://mathoverflow.net/questions/40618/uncomputability-of-...


So what? Equality of floating point numbers is only "decidable" if you don't care about getting the right answer.

Likewise, equality of functions is also undecidable, but you never see people bringing that up in the context of Higher Order Functions.


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

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.


You can compute on any real number you're given, but IIUC that's not what "computability" means. By the cardinality argument above (there are more infinite streams of digits than finite streams of digits, in an important sense) there will exist streams of digits that you cannot produce by any program (regardless of how you encode it).


You can produce an arbitrary infinite stream using a random number generator, for instance.


The probability of generating any given infinite stream is 0, though.


But, assuming you have a true random number generator, so is the probability that a stream you generate is computable.


Yes.


Where is the fallacy? I don't doubt type-2 effectivity is used in the way you mention, but that wasn't what I was talking about. See my other reply.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: