19
$\begingroup$

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?

$\endgroup$
17
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I am almost entirely ingnorant on exact real arithmetic, but couldn't one implement Kahan summation in it? $\endgroup$ – jjg Jul 16 '15 at 10:54
  • 1
    $\begingroup$ Hmm, I don't think so. Think of exact real arithmetic as interval arithmetic that self-adjusts intermediate precision to achieve the desired output precision. $\endgroup$ – Andrej Bauer Jul 16 '15 at 13:19
  • 3
    $\begingroup$ In addition to lack of understanding by programmers on the fact that real numbers are infinite objects and its consequences for what can be done programmatically, I think lack of hardware support is also important. It is hard to convince people to use something with significant time and memory overhead just for correctness. $\endgroup$ – Kaveh Jul 16 '15 at 14:51
  • 1
    $\begingroup$ I saw that there's some activity in implementing real computation with coinductive types. It feels to me that coinductive types are still quite tricky to get right (I'm certainly no expert in it), but do you think this holds promise for more widespread use of exact real computation? $\endgroup$ – SorcererofDM Jul 16 '15 at 20:02
  • 3
    $\begingroup$ Any implementation which uses streams of digits, or anything else that has a fixed rate of convergence, is handicapped from the outset in that it will converge too slowly. Also, stream-based implementations tend to force you to calculate all the previous approxmations to get the next one, which is also a design mistake as well. $\endgroup$ – Andrej Bauer Jul 16 '15 at 23:50
10
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ are there any proven gaps between some form of exact real computation and floating point computation? $\endgroup$ – SorcererofDM Jul 17 '15 at 18:01
  • 1
    $\begingroup$ Not that I know of, I'm afraid. Sean Gao has some interesting results on the complexity of approximate decision procedures over the reals (see his thesis abstract) and of course the denominator in the inverse of a matrix grows at worst like its determinant. $\endgroup$ – cody Jul 17 '15 at 18:10
-6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.