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

<p>The community of people who work on exact real arithmetic consists of theoreticians who are not used to developing software. So they usually <a href="http://www.dcs.ed.ac.uk/home/mhe/plume/">relegate the task of implementation to students</a> (a notable exception is Norbert Müller's <a href="http://irram.uni-trier.de">iRRAM</a>), or they have their own <a href="https://github.com/andrejbauer/marshall">toy implementations</a>.</p>

<p>People who <em>do</em> 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 <code>for</code> 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 <code>&lt;</code> and <code>=</code> as total boolean function on the reals simply do not exist (you can have <code>=</code> but it either returns <code>false</code> or it diverges, and <code>&lt;</code> diverges when given two equal reals).</p>

<p>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 <code>main</code>), 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 <code>Staged</code> monad (which is essentially the <code>Reader</code> monad). Most people expect the real numbers to be "just another datatype", but I have my doubts about that.</p>

CC BY-SA 3.0
2015-07-16T10:54:03.897Z
I am almost entirely ingnorant on exact real arithmetic, but couldn't one implement Kahan summation in it?
jjg
CC BY-SA 3.0
2015-07-16T13:19:34.457Z
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.
Andrej Bauer
CC BY-SA 3.0
2015-07-16T14:51:35.183Z
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.
Kaveh
CC BY-SA 3.0
2015-07-16T15:22:59.137Z
Good point. In fact, it's difficult to change the floating point format for the same reason: hardware manufacturers see no point in it so they don't do it. But recently there's been new motivation: by improving FP format they can save electricity. Let's hope for the best.
Andrej Bauer
CC BY-SA 3.0
2015-07-16T20:02:53.573Z
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?
SorcererofDM
CC BY-SA 3.0
2015-07-16T23:50:00.947Z
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.
Andrej Bauer
CC BY-SA 3.0
2015-07-17T18:33:36.730Z
So what are the alternatives? Dedekind cuts? Can you recommend some references?
SorcererofDM
CC BY-SA 3.0
2015-07-19T20:30:41.927Z
An alternative is to use intervals of some sort as an approximation and a `Reader` monad for the output (or input) precision. You can then start your computation on and desired output (or input) precision without waiting for the stream to get there. iRRAM does something like this, for instance.
Andrej Bauer
CC BY-SA 3.0
2015-07-16T08:34:44.363Z
2015-07-16T08:41:06.093Z
2015-07-16T08:41:06.093Z
Andrej Bauer
<p>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.</p>

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

<p>The application that springs to mind is the use of <a href="https://en.wikipedia.org/wiki/Computational_fluid_dynamics">computational fluid dynamics</a> to design the aerodynamics of cars or planes, where small errors in computation are easily made up with the astronomical gains of using dedicated <a href="https://en.wikipedia.org/wiki/Floating-point_unit">floating point units</a> found in many widespread processors.</p>

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

<p>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 <a href="http://wstein.org/books/modform/modform/linear_algebra.html">here</a> 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 <a href="https://en.wikipedia.org/wiki/List_of_optimization_software">here</a>).</p>

CC BY-SA 3.0
2015-07-17T18:01:31.243Z
are there any proven gaps between some form of exact real computation and floating point computation?
SorcererofDM
CC BY-SA 3.0
2015-07-17T18:10:22.227Z
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](http://scungao.github.io/papers/thesis_extended_abstract.pdf)) and of course the denominator in the inverse of a matrix grows at worst like its [determinant](https://en.wikipedia.org/wiki/Invertible_matrix#In_relation_to_its_adjugate).
cody
CC BY-SA 3.0
2015-07-17T17:34:27.197Z
2015-07-17T17:34:27.197Z
cody
<p>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)</p>

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

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

CC BY-SA 3.0
2015-07-17T14:36:27.177Z
2015-07-17T14:36:27.177Z
david rush
<p>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?</p>

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

<cc.complexity-theory><computing-over-reals><computable-analysis><domain-theory>
Computation of reals: floating point vs TTE vs domain theory vs etc
SorcererofDM
# Computation of reals: floating point vs TTE vs domain theory vs etc

(Asked by: username_0 on 2015-07-16)

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?

**Tags:** cc.complexity-theory, computing-over-reals, computable-analysis, domain-theory


---

## 3 answers

### Answer by username_1 on 2015-07-16. Score: 18

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](http://www.dcs.ed.ac.uk/home/mhe/plume/) (a notable exception is Norbert Müller's [iRRAM](http://irram.uni-trier.de)), or they have their own [toy implementations](https://github.com/andrejbauer/marshall).

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.

> **Comments:**
> **username_2**: I am almost entirely ingnorant on exact real arithmetic, but couldn't one implement Kahan summation in it?  
> **username_1**: 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.  
> **username_3**: 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.  
> **username_1**: Good point. In fact, it's difficult to change the floating point format for the same reason: hardware manufacturers see no point in it so they don't do it. But recently there's been new motivation: by improving FP format they can save electricity. Let's hope for the best.  
> **username_0**: 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?  
> **username_1**: 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.  
> **username_0**: So what are the alternatives? Dedekind cuts? Can you recommend some references?  
> **username_1**: An alternative is to use intervals of some sort as an approximation and a `Reader` monad for the output (or input) precision. You can then start your computation on and desired output (or input) precision without waiting for the stream to get there. iRRAM does something like this, for instance.  

---

### Answer by username_4 on 2015-07-17. Score: 10

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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Floating-point_unit) 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](http://wstein.org/books/modform/modform/linear_algebra.html) 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](https://en.wikipedia.org/wiki/List_of_optimization_software)).

> **Comments:**
> **username_0**: are there any proven gaps between some form of exact real computation and floating point computation?  
> **username_4**: 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](http://scungao.github.io/papers/thesis_extended_abstract.pdf)) and of course the denominator in the inverse of a matrix grows at worst like its [determinant](https://en.wikipedia.org/wiki/Invertible_matrix#In_relation_to_its_adjugate).  

---

### Answer by username_5 on 2015-07-17. Score: -6

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


---

