infinite (fractional) precision

Jerzy Karczmarczuk karczma@info.unicaen.fr
Thu, 10 Oct 2002 11:50:39 +0200


Ashley Yakeley wrote:

> I considered doing something very like this for real (computable)
> numbers, but because I couldn't properly make the type an instance of Eq,
> I left it. Actually it was worse than that. Suppose I'm adding two
> numbers, both of which are actually 1, but I don't know that:
> 
>  1.000000000.... +    0.999999999....
> 
> The trouble is, as far as I know with a finite number of digits, the
> answer might be   1.9999999999937425   or it might be  2.0000000000013565
> 
> ...so I can't actually generate any digits at all. So I can't even make
> the type an instance of my Additive class.

You can, unless you are so ambitious that you want to have an ideal solution.
Doing the stuff lazily means that you will have a thunk used in further
computations, and the digits will be generated according to your needs.

You *MAY* generate these digits physically ('1' or '2' in your case) if you
permit yourself to engage in a possibly bottom-less recursive pit, which
in most interesting cases actually *has* a bottom, and the process stops.
Please look my "Pi" crazy essay. Once the decision concerning the carry is
taken, the process becomes "sane", generative, co-recursive, until the next
ambiguity.

There are of course more serious approaches: intervals, etc. The infinite-
precision arithmetic is a mature domain, developed by many people. Actually
the Gosper arithmetic of continued fractions is also based on co-recursive
expansion, although I have never seen anybody implementing it using a lazy
language, and a lazy protocol.

Anybody wants to do it with me? (Serious offers only...)

Jerzy Karczmarczuk