The only problem with representations of this kind is one of efficiency. If a sequence of rationals is used, then at each point in the sequence we are replicating information already delivered, together with another small piece of information narrowing the bound of error.

It is plausible that a representation more like a positional notation, or a continued fraction notation will yeild more efficient implementations because they do not reiterate information already delivered earlier in the sequence.

An alternative representation may be found by reference to the literature on constructive analysis. For example Bishop85 talks of a real number as a regular sequence of rationals A sequence is regular if the difference between the nth and mth elements in the sequence is not greater than (1/m+1/n). Modifiying this to give computable reals as algorithms which generate regular sequences of rationals gives a representation over which addition is computable.

This representation is likely to be inefficient because of its slow rate of convergence.

Its a lot easier to come up with a representation for the computable reals than to come up with one that works.

For a representation of the computable reals to work properly its not sufficient for the representations of the computable reals to be computable. All the operations which one would expect to be computable over the computable reals (which is probably the same as the constructive functions over constructive reals) must also be computable over the chosen representatives. For a pretty complete picture of the ones which should be computable look at a text on constructive analysis, e.g. Bishop85. That happens to include things like addition, subtraction, multiplication, division (except by zero) and lots lots more. And effective means that they never go into unproductive loops, not just infrequently. Get your representation wrong and you algorithms will sulk indefinitely on some problems.

So you should ask yourself, first of all, when you are about to adopt a representation, whether addition is effective over the representatives. And then go on to ask whether the other operations are.

This might seem a pretty obvious requirement, but neither the most obvious (n-ary positional expansions for some integer n>1), nor what appears to have recently been the most popular (continued fractions) ways of representing computable reals satisfy this criterion. Both of these do provide computable representatives of all the computable reals, so they determine the right subset of the reals in a computable way. However over neither of these representations is even the most elementary operation, addition, effective.

Signed decimal expansions. This works. It is a wide-10ary expansion.

1. The denominators of the rationals are all positive integer powers of some base B.
2. The rate of convergence is fixed by the requirement that the nth B-adic in the sequence is within 1/(Bⁿ) of the real answer.

What we need is a representation which makes the operations computable and efficient (insight!).

I have two preferences:

1. Floating point infinite positional expansions with signed digits using a very large base (e.g. 2³²). Because of the large granularity you need to have ways of putting together higher level operations (e.g. summing infinite sequences) which do not build on the primitive two-operand addition. Pietro di Gianontonio discusses large base representations and the resulting granularity problems, proposing a different approach to their resolution which I have not yet grasped.
2. A signed n-ary expansion with a variable base (a power of two). When you want another "digit" you say how much precision you are looking for, (number of bits) and you get back exactly what you asked for (plus a sign). This is to get the advantages of computing with large chunks while avoiding the problems of large granularity.

   Here's the rationale.

   1. Its incremental
   2. If you ask for a lot it will make effective use of the arithmetic hardware.
   3. The precision demanded from subsidiary computations need not be more than necessary
   If in order to realise benefit (2) you chose a fixed very large base (say 2^64), then little benefit will accrue, since the precision required in the operands will grow just as rapidly (in terms of number of "digits") as if the base were small.

   If the base is variable then where 32 bit precision is required it can be realised using the hardware, but the small increments in precision required for subsidiary computations to realise the required precision in the result are not exaggerated to negate the benefit of using the hardware.

   However this is hard to make work.

   ---

   © created 1995/9/3 modified 1999/4/28