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

Toward an API for the Real Numbers

blog.acolyer.org

Post reply on HN
Print view View original

31–40 of 85 posts

Re: Toward an API for the Real Numbers

#31

Post by comex »

qsort wrote: post #19
slx26 wrote: post #12

In "safe" languages we often talk about how you can't ignore errors in return values. Your program "leaks" if that happens. But with integer overflows and floating point precision, we just ignore the leaks as something that programmers already know about and have to consider while coding. Of course, it's not an easy problem to deal with, as computers don't have infinite memory and they need to be performant, but we r…

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

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

Re: Toward an API for the Real Numbers

#32

Post by millstone »

qsort wrote: post #29
millstone wrote: post #26

Earlier quoted context omitted.

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, t…

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.

Re: Toward an API for the Real Numbers

#33

Post by qsort »

millstone wrote: post #32
qsort wrote: post #29

Earlier quoted context omitted.

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, t…

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.

Re: Toward an API for the Real Numbers

#34

Post by philzook »

Fun fact: The Boehm of this paper is the same Boehm as the garbage collector

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

Re: Toward an API for the Real Numbers

#35

Post by erichocean »

qsort wrote: post #19
slx26 wrote: post #12

In "safe" languages we often talk about how you can't ignore errors in return values. Your program "leaks" if that happens. But with integer overflows and floating point precision, we just ignore the leaks as something that programmers already know about and have to consider while coding. Of course, it's not an easy problem to deal with, as computers don't have infinite memory and they need to be performant, but we r…

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

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

Re: Toward an API for the Real Numbers

#36

Post by fouronnes3 »

skulk wrote: post #4
qppo wrote: post #3

What about NaN values? Are the runtime errors or do they propagate down the chain of execution? Are they comparable?

For a high-level API, shouldn't this be expressed with types such as a `Result ` at the library level? edit: now that I think about it, that would require some really nice optional chaining syntax to be even slightly usable.

Oh now I'm curious if IEEE 754 NaN rules are isomorphic to a number optional type with monadic chaining syntax

Re: Toward an API for the Real Numbers

#37

Post by qsort »

comex wrote: post #31
qsort wrote: post #19

Earlier quoted context omitted.

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

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

Re: Toward an API for the Real Numbers

#38

Post by dchapp »

taylodl wrote: post #21

IEEE 754. If you're going to do any serious computation in floating point, serious meaning people's lives are going to depend on the outcome or a lot of money is on the line, then you MUST know what you're doing. We have standards in place so people can learn it, people creating math libraries can adhere to it, and those creating these kinds of applications can have confidence that things are going to work. I'm sorry…

> I'm sorry addition isn't commutative...

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

Re: Toward an API for the Real Numbers

#39

Post by qsort »

erichocean wrote: post #35
qsort wrote: post #19

Earlier quoted context omitted.

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

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

Re: Toward an API for the Real Numbers

#40

Post by molyss »

fanf2 wrote: post #8
neolog wrote: post #5

Earlier quoted context omitted.

There are no NaN values in the real numbers.

You need some way to cope with operations that don’t have real results for some values, such as log and sqrt of negative numbers

you can just represent those as a pair of real numbers, one for the real part, and one for the imaginary part. As long as you only (recursively) apply exponential and trig functions on those numbers, I believe you'll stay within the realm of complex numbers.
Post reply on HN