Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Current floating point (ANSI C float, double) allow to represent an approximation of a real number.
Is there any way to represent real numbers without errors?
Here's an idea I had, which is anything but perfect.

For example, 1/3 is 0.33333333...(base 10) or o.01010101...(base 2), but also 0.1(base 3)
Is it a good idea to implement this "structure":

base, mantissa, exponent

so 1/3 could be 3^-1

{[11] = base 3, [1.0] mantissa, [-1] exponent}

Any other ideas?

share|improve this question
9  
You will only be able to represent rational numbers this way. –  Andrej Bauer Jul 12 at 8:36
    
How do you propose to implement arithmetic operations on numbers in this representation? Using logarithms to change base? This would be much more expensive than IEEE floating-point math. –  David Zhang Jul 14 at 20:33
    
Well, I've no idea. I'm not an engineer :) Obviously, I cannot implement it in hardware. A slow, unefficient implementation can be done in C. This would be just an experiment –  Mignus Jul 15 at 6:56
add comment

9 Answers 9

up vote 16 down vote accepted

It all depends what you want to do.

For example, what you show is a great way of representing rational numbers. But it still can't represent something like $\pi$ or $e$ perfectly.

In fact, many languages such as Haskell and Scheme have built in support for rational numbers, storing them in the form $\frac{a}{b}$ where $a,b$ are integers.

The main reason that these aren't widely used is performance. Floating point numbers are a bit imprecise, but their operations are implemented in hardware. Your proposed system allows for greater precision, but requires several steps to implement, as opposed to a single operation that can be performed in hardware.

It's known that some real numbers are uncomputable, such as the halting numbers. There is no algorithm enumerating its digits, unlike $\pi$, where we can calculate the $n$th digit as long as we wait long enough.

If you want real precision for things irrational or transcendental numbers, you'd likely need to use some sort of system of symbolic algebra, then get a final answer in symbolic form, which you could approximate to any number of digits. However, because of the undecidability problems outlined above, this approach is necessarily limited. It is still good for things like approximating integrals or infinite series.

share|improve this answer
    
May I ask another question? If you had been an Intel engineer in the 80s, how would you have "designed" your real number format? –  Mignus Jul 11 at 21:03
1  
I'm not very qualified to answer that, as I'm not an engineer, I'm a theory researcher. I don't see much wrong with IEEE float and double standards, and now quad. I don't think there have been many applications depending on higher precision arithmetic, and those that do can use a software-supported version. –  jmite Jul 11 at 21:06
    
Symbolic algebra is not the correct formalism for exact real arithmetic. You need a representation which allows arbitrarily large mantissas. –  Andrej Bauer Jul 12 at 8:37
5  
@AndrejBauer: An arbitrarily large mantissa isn't going to save you if you want an exact representation of $\sqrt 2$. –  user2357112 Jul 12 at 9:16
    
@jmite you're too much modest :) –  Mignus Jul 12 at 17:25
show 3 more comments

There is no way to represent all real numbers without errors if each number is to have a finite representation. There are uncountably many real numbers but only countably many finite strings of 1's and 0's that you could use to represent them with.

share|improve this answer
    
One could restrict the requirement from representing every real number to only restricting those real numbers, which could be the output of a turing machine. That would only be a countable number of real numbers, but would still cover every number you would ever want to represent. But I don't think you could do efficient computations with such numbers. –  kasperd Jul 11 at 22:30
3  
@kasperd They're called computable reals. Unfortunately, things like equality aren't computable over the computable reals. –  David Richerby Jul 11 at 22:41
    
It is indeed quite clear that computing equality on such numbers is equivalent to solving the halting problem. Given a TM one can define a real number, which starts with a lot of decimals that are zero, exactly as many as the running time of the TM, and then followed by a one. Comparing that number to zero is equivalent to solving the halting problem for the original TM. –  kasperd Jul 11 at 23:34
    
This answer is false. Alan Turing in his first paper on machines, the ones in which he invents Turing machines, talks about representing reals as infinite strings of data. This leads to the idea of so-called "Type II Turing machine", and there is a very succesful theory of real-number computation based on the idea. It is also implemented in practice, see my answer. –  Andrej Bauer Jul 12 at 9:03
1  
Perhaps it does technically, but it misses the point, which is that there are perfectly reasonable infinite representations of real numbers. And that's nothing strange: a TCP/IP connection, or a Skype call, or a video feed from a camera are all examples of (potentially) infinite amount of data. There is no a priori limitation on how much information they can provide. There is only a limitation on how much information you can get out of it in a finite amount of time. –  Andrej Bauer Jul 12 at 11:31
show 1 more comment

There are many effective Rational Number implementations but one that has been proposed many times and can even handle some irrationals quite well is Continued Fractions.

Quote from Continued Fractions by Darren C. Collins:

Theorem 5-1. - The continued fraction expression of a real number is finite if and only if the real number is rational.

Quote fromMathworld - Periodic Continued Fractions

... a continued fraction is periodic iff it is a root of a quadratic polynomial.

i.e. all roots can be expressed as periodic continued fractions.

There is also an Exact Continued Fraction for π which surprised m e until @AndrejBauer pointed out that it actually isn't.

share|improve this answer
    
Your last sentence is misleading. There is no finite (or periodic) continued fraction for $\pi$. The continued fraction for $\pi$ is infinite and aperiodic. –  D.W. Jul 12 at 1:57
    
Continued fractions representation of reals was proposed as an implementation for exact real arithmetic a while ago by J. Vuillemin. It turns out not to be very efficient as the numbers get pretty big pretty soon, and it's hard to cut down on their size. –  Andrej Bauer Jul 12 at 9:01
    
Continued fractions have some computational issues even for representing rational numbers - while they can be compared relatively quickly using a variant of lexicographic order, and while manipulating a single continued fraction is easy, both (binary) addition and multiplication on CFs are fairly complicated operations to implement. –  Steven Stadnicki Jul 13 at 2:54
add comment

Your idea does not work because a number represented in base $b$ with mantissa $m$ and exponent $e$ is the rational number $b \cdot m^{-e}$, thus your representation works precisely for rational numbers and no others. You cannot represent $\sqrt{2}$ for instance.

There is a whole branch of computable mathematics which deals with exact real arithmetic. Many data structures for representing exact real numbers have been proposed: streams of digits, streams of affine contractions, Cauchy sequences of rationals, Cauchy sequences of dyadic rationals, Dedekind cuts, sequences of shkrinking intervals, etc. There are implementations of exact real arithmetic based on these ideas, for instance:

Of these iRRAM is the most mature and efficient. Marshall in an experimental project, while the third one is a student project, but also the most easily accessible one. It has a very nice introduction explaining the issues regarding real number computation, I highly recommed that you look at it.

Let me make a remark. Someone will object that an infinite object cannot be represented by a computer. In some sense this is true, but in another it is not. We never ever have to represent an entire real number, we only need a finite approximation at each stage of the computation. Thus, we only need a representation which can represent a real up to any given precision. Of course, once we run out of computer memory we run out of computer memory -- but that is a limitation of the computer, not the representation itself. This situation is no different than many others in programming. For instance, people use integers in Python and they think of them as "arbitrarily large" even though of course they cannot exceed the size of available memory. Sometimes infinity is a useful approximation for a very large finite number.

Furthermore, I often hear the claim that computers can only deal with computable real numbers. This misses two important points. First, computers have access to data from the external world, so we would also have to make (the unverifiable) assumption that the external world is computable as well. Second, we need to distinguish between what reals a computer can compute, and what reals it can represent. For instance, if we choose streams of digits as the representation of reals then it is perfectly possible to represent a non-computable real: if someone gave it to us we would know how to represent it. But if we choose to represent reals as pieces of source code that compute digits, then we could not represent non-computable reals, obviously.

In any case, this topic is best tackled with some further reading.

share|improve this answer
    
+1 but I would object that you can't represent an infinite string by a finite approximation without losing precision, as required by the question. Sure, you can get as much precision as you want -- as you could by approximating by a rational -- but that's not quite what the question's asking for. Arguably, that's a problem with the question, rather than the answer. –  David Richerby Jul 12 at 9:17
    
The point is that we are not representing with finite strings. We are representing with infinite strings, but we only ever need a finite portion of such an infinite string at each stage of computation. Or to put it another way: there is no loss of precisions, as the data structure holds the entire information, but of course you cannot access or process all of the information at once: the data structure gives you as much precision as you ask for. The bottleneck is not on the side of the data structure, but rather on the side of the "consumer" who want to get the information out of it. –  Andrej Bauer Jul 12 at 11:25
    
@AndrejBauer But you must access or process all the information at once in some cases, e.g. this is what symbolic computation does, by capturing the "essence" or nature of a quantity rather than just as any other stream of digits. If you tell a symbolic computation package to verify that $\sqrt{2}^2 = 2$, it would instantly output true. If you used the method you seem to describe, by taking the first $k$ digits of the square root of $2$, for any $k$ you will conclude that $\sqrt{2}^2 \ne 2$ as your result will (for any finite $k$) equal $1.99...$, wrong answer. Computations are finite. –  Thomas Jul 12 at 13:50
    
@Thomas Remember that the stream of digits is a representation of numbers. Equality of the numbers is not equivalent with equality of the streams. What you need to do is not “process all the information”, but decide based on finite information. If you approximate a stream of digits with an initial sequence of its values, this approximation is not good enough to decide equality. –  Gilles Jul 12 at 16:10
    
@Thomas: symbolic computation does not represent real numbers, but usually some subfield of the reals, typically the one generated by elementary functions and roots of polynomials. These subfields are not complete (closed under limits of Cauchy sequences) nor computably complete (closed under computable limits of Cauchy sequences). A representation is not a representation of reals unless you can represent all (computable) reals: and symbolic computations fails this condition. –  Andrej Bauer Jul 14 at 8:23
add comment

There are a number of "exact real" suggestions in the comments (e.g. continued fractions, linear fractional transformations, etc). The typical catch is that while you can compute answers to a formula, equality is often undecidable.

However, if you're just interested in algebraic numbers, then you're in luck: The theory of real closed fields is complete, o-minimal, and decidable. This was proven by Tarski in 1948.

But there's a catch. You don't want to use Tarski's algorithm, since it's in the complexity class NONELEMENTARY, which is as impractical as impractical algorithms can get. There are more recent methods which get the complexity down to DEXP, which is the best we currently know.

Note that the problem is NP-hard because it includes SAT. However, it's not known (or believed) to be in NP.

EDIT I'm going to try to explain this a little more.

The framework for understanding all of this is a decision problem known as Satisfiability Modulo Theories, or SMT for short. Basically, we want to solve SAT for a theory built on top of classical logic.

So we start with first order classical logic with an equality test. Which function symbols we want to include and what their axioms are determine whether or not the theory is decidable.

There are lots of interesting theories expressed in the SMT framework. For example, there are theories of data structures (e.g. lists, binary trees, etc) which are used to help prove programs correct, and the theory of Euclidean geometry. But for our purpose, we're looking at theories of different kinds of number.

Presburger arithmetic is the theory of natural numbers with addition. This theory is decidable.

Peano arithmetic is the theory of natural numbers with addition and multiplication. This theory is not decidable, as famously proven by Gödel.

Tarski arithmetic is the theory of the real numbers with all field operations (addition, subtraction, multiplication, and division). Interestingly, this theory is decidable. This was a highly counter-intuitive result at the time. You might assume that because it's a "superset" of the natural numbers it's "harder", but this isn't the case; compare linear programming over the rationals with linear programming over the integers, for example.

It may not seem obvious that satisfiabilty is all you need, but it is. For example, if you want to test whether or not the positive square root of 2 is equal to the real cube root of 3, you can express this as the satisfiability problem:

$$\exists x. x>0 \wedge x^2 - 2 = 0 \wedge x^3 - 3 = 0$$

So then there's the question as to what other operations you can add to Tarski arithmetic and still keep decidability. The next obvious things to add are elementary transcendental operations like $e^x$, and the trigonometric functions.

It turns out that the theory of reals with $\sin$ is undecidable, because $\{ \frac{x}{\pi} | \sin x = 0 \}$ is the integers. Given the reals and $\sin$, you can construct the theory of integers, and the theory of integers is undecidable.

Tarski conjectured that real fields plus $e^x$ is undecidable. I don't know if anyone has proven that it isn't decidable, but I know that nobdody has yet proven that it is decidable. He believed that the reason why this is likely is because of what happens in the complex plane; if you have $e^{ix}$, then you automatically have trigonometry.


Alfred Tarski (1948), A Decision Method for Elementary Algebra and Geometry.

share|improve this answer
add comment

It's possible to represent a very large class of numbers called algebraic numbers exactly, by treating them as roots of polynomials.

This article as well as this mathoverflow question have more information, as well as many more resources about this topic. As far as I know, this method still fails to represent transcendental numbers such as $\pi$ or $e$, unless some generalization of it has been discovered. There are many other issues with this method, such as additional solutions to simple addition appearing out of "nowhere" (also known as the complex plane). It's a tradeoff, use your good judgement to tell if it's useful for you.

share|improve this answer
    
Tarski conjectured (and I haven't seen anything in the last 60 years which either agreed or disagreed with it) that closed real fields with $e$ is undecidable, because of what happens in the complex plane. Once you have $e^{ix}$, you have $\sin$ and $\cos$, and $\{ x \in \mathbb{R} | \sin x = 0 \}$ constructs something that's close enough to the integers that it's undecidable (per Gödel). –  Pseudonym Jul 13 at 8:29
    
@Pseudonym This seems really interesting, but I don't think I have the mathematical background to understand it properly... What do you mean by "close enough to the integers"? –  More Axes Jul 13 at 8:35
    
I'm going to amend my answer to explain. –  Pseudonym Jul 13 at 22:02
add comment

There is no way to represent a real number since they cannot really be represented in the real world. We can give approximations of them, arbitrary symbols for them like $\pi$, or ways to get them like $\sqrt2$, but there actual value can never be truly represented. You would have to start dealing with them purely symbolically and hope they factor out. However even them, there is no way to account for all of them since as David said, there is not enough strings to give these symbolic representations.

share|improve this answer
    
This answer is false. There is a whole area of exact real arithmetic which explains how to represent reals by computers. The assumption that a real must be represented by a finite string is mistaken. We can also use infinite strings. Already Alan Turing wrote about this in his first paper, the one where he invented Turing machines! –  Andrej Bauer Jul 12 at 8:59
    
Can you link to a paper about how to store and manipulate infinate strings in an actual computer, because that would be the answer to what the question asked. Also it wasnt his first paper, first publication was 1936, that paper was 1937. –  lPlant Jul 12 at 17:42
    
You're right it's the 1937 paper. To see how infinite strings are manipulated, you can look at the TCP/IP protocol, for instance. I never said the whole real must be stored in the computer. –  Andrej Bauer Jul 14 at 8:24
add comment

You cannot represent all real numbers in a computer, but you can represent many. You could use fractions which would represent more numbers than floats. You could also do more sophisticated things like representing numbers as a root of some polynomial with an approximation that under newtons method will converge to the number.

share|improve this answer
    
This again is a false answer, produced out of ignorance. There is a whole area of exact real arithmetic which studies how to represent all reals by suitable data structures. –  Andrej Bauer Jul 12 at 11:26
    
@AndrejBauer So you are suggesting there is a data structure that can represent any real number? Any such data structure would have to use an uncountable infinite amount of bits to represent any number. –  Darksonn Jul 12 at 11:48
1  
A countable amount of bits suffices, first of all, and since you don't need all of them at once, nor are you able to process them all at once, they can be stored in time as well as space. –  Andrej Bauer Jul 12 at 11:50
    
@AndrejBauer This answer is correct, and saying the same thing as yours, albeit with a lot less information. You cannot represent all real numbers in a computer. You can represent any real number, but not all at once. If anything, I would dispute that you can represent “many”, since you can only represent finitely many in any given computer, and only almost none (in the mathematical sense) in an abstract computer that is equivalent to the usual computation models (Turing machine equivalent). –  Gilles Jul 12 at 16:12
add comment

It is possible to represent any number precisely where the inputs are representable by storing them as a string of operations so, for example, you store 1/3 as 1 divided by 3, by handling cancelling of operations you can simplify the next operation to give an exact answer for (1/3) * 3. This can also handle situations where you have known irrationals such as π by retaining it in your calculations.

However, it requires an increasing amount of memory for each number and - assuming your simplifier isn't perfect - it'll probably require an ever increasing amount for values you're working on a lot.

share|improve this answer
    
It's extremely unclear that you always know when or how to cancel operations. It's not always as easy as "1/3 * 3 = 1", e.g. $\sqrt{5 + 2\sqrt{6}} - \sqrt{2} = \sqrt{3}$. –  Ben Millwood Jul 13 at 22:04
    
Indeed. In fact, it's probably effectively impossible to automate completely successfully. However, the result remains precise even if you've not used the simplest possible representation. –  Jack Aidley Jul 14 at 7:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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