Computation of reals: floating point vs TTE vs domain theory vs etc

Question

Currently, computation of reals in most popular languages is still done via floating point operations. On the other hand, theories like type two effectivity (TTE) and domain theory have long promised exact computation of reals. Clearly, the problem of floating point precision has not dwindled in relevance, so why haven't these theories become more mainstream and why aren't there more conspicuous implementations of them?

For example, are there domains of applications where we don't care much about floating point errors? Are there significant complexity concerns?

Answer 1

I work in real-number computation, and I wish I knew the real answer. But I can speculate. It's a sociological problem, I think.

The community of people who work on exact real arithmetic consists of theoreticians who are not used to developing software. So they usually relegate the task of implementation to students (a notable exception is Norbert Müller's iRRAM), or they have their own toy implementations.

People who do have the necessary programming mojo do not have the necessary theoretical background. Without solid theoretical footing it is difficult to design exact real arithmetic correctly. For instance, it is a mistake to add lots of real numbers in a for loop, as you will get unacceptable performace due to loss of precision. If you want to add lots and lots of reals, you should do it with a tree-like structure, taking into account the magnitudes of the partial sums. Another thing which is difficult to get across is that < and = as total boolean function on the reals simply do not exist (you can have = but it either returns false or it diverges, and < diverges when given two equal reals).

Lastly, it is not clear at all that we know how to implement libraries for exact real arithmetic. They're not the usual pieces of libraries which just define some datatypes and some functions on them. Often exact real arithmetic requires special modes of control. For instance, iRRAM takes over the main execution of the program (it literally hijacks main), as well as standard input and output, so that it can rerun the program when loss of precision occurs. My library for real arithmetic in Haskell happens in a Staged monad (which is essentially the Reader monad). Most people expect the real numbers to be "just another datatype", but I have my doubts about that.

Answer 2

In general, people always care about floating point errors. However I disagree with Andrej, and I do not think that floats are preferred to arbitrary precision reals (for the most part) because of sociological reasons.

I believe the main argument against exact computation of reals is one of performance. So the short answer is, whenever performance is more important than precision, you'll want to use floating point numbers.

The application that springs to mind is the use of computational fluid dynamics to design the aerodynamics of cars or planes, where small errors in computation are easily made up with the astronomical gains of using dedicated floating point units found in many widespread processors.

In particular, the problem of representing a wide range of real numbers using a fixed number of bits is not as trivial as it may seem at first glance. In numerical simulation, values may vary widely (e.g. when there is turbulence), so fixed-point computations aren't appropriate.

Even when precision is not fixed by the hardware, using arbitrary precision numbers can be several orders of magnitude slower than using floating point numbers. In fact, even in the nice case were all the numbers are rational, simple operations like inverting a matrix can result in large, hard to control denominators (see here for an example). Many large linear optimization packages use floating points with appropriate rounding modes to find approximate solutions because of this exact issue (see for example, the majority of programs found here).

Answer 3

I am hardly an expert, but I have been honing my chops on this over the last few years. The problem is that the "real" numbers simply do not exist in the same way that natrual numbers do. Is there anyone who has an intuitive grasp of "$\pi$-ness"? Essentially the real numbers are defined by various limit processes; many of these limit processes have been given special names, and some of them are special enough that they form significant subsets of the reals (e.g. algebraic numbers)

My point being that if you are going to compute exactly, you have to have placeholders for the special names as well as the familiar names the naturals. At some point you are going to want to approximate the exact value in order to apply it to something in the real world. As it turns out, it is much more efficient to just deal with the whole problem as approximations from the start, unless you have very specialized needs.

Of course, very few working programmers think this way. They mostly say to themselves "Gee, double has more precision than I could possibly ever, might as well use it", and mostly that is the most economical approach. The problem is that most programmers don't know how to spot when they are getting into trouble because the set of double-precision floats is infinitely smaller than $R$...