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

51–60 of 85 posts

Re: Toward an API for the Real Numbers

#51

Post by ogogmad »

dahart wrote: post #41
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…

> In "safe" languages we often talk about how you can't ignore errors in return values. 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…

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

Arbitrary precision is very different from exact real arithmetic.

Re: Toward an API for the Real Numbers

#52

Post by ogogmad »

alentist wrote: post #28
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.

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.

Re: Toward an API for the Real Numbers

#53

Post by [deleted] »

qsort wrote: post #33
millstone wrote: post #32

Earlier quoted context omitted.

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

[deleted]

Re: Toward an API for the Real Numbers

#54

Post by molyss »

flubert wrote: post #46
molyss wrote: post #40

Earlier quoted context omitted.

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.

0/0, tan(pi/2), log(0)

I was replying to the sqrt and log of negative numbers. For undefined functions, I'd throw an exception

Re: Toward an API for the Real Numbers

#55

Post by _ouml_ »

modeless wrote: post #6

Looks like a cool library. I'm curious why the Android calculator app needs reliable exact equality tests. It doesn't appear to have an equality test function. 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.

The equality test is equivalent to deciding if something is 0. You can probably ask the app to calculate sqrt(2) * sqrt(2). If that doesn't show a 2 as answer, you've lost. Same goes for sin(arcsin(1/2)). You want the exact answer.

Re: Toward an API for the Real Numbers

#56

Post by moonchild »

philzook wrote: post #34

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

> Boehm

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.

Re: Toward an API for the Real Numbers

#57

Post by dllthomas »

ogogmad wrote: post #49
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…

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

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

Re: Toward an API for the Real Numbers

#58

Post by qsort »

ogogmad wrote: post #49
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…

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

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.

Re: Toward an API for the Real Numbers

#59

Post by est31 »

qsort wrote: post #39
erichocean wrote: post #35

Earlier quoted context omitted.

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

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.

Re: Toward an API for the Real Numbers

#60

Post by lmm »

qsort wrote: post #33
millstone wrote: post #32

Earlier quoted context omitted.

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

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

Post reply on HN