infinite (fractional) precision

Dylan Thurston
Thu, 10 Oct 2002 20:22:07 -0400

Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Thu, Oct 10, 2002 at 02:25:59AM -0700, Ashley Yakeley wrote:
> At 2002-10-10 01:29, Ketil Z. Malde wrote:
> >I realize it's probably far from trivial, e.g. comparing two equal
> >numbers could easily not terminate, and memory exhaustion would
> >probably arise in many other cases.
> I considered doing something very like this for real (computable)=20
> 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=20
> numbers, both of which are actually 1, but I don't know that:
>  1.000000000.... +
>  0.999999999....
> ...

The solution to such quandries is to allow non-unique representation.
For instance, you might consider a binary system with allowed digits +1,
0, and -1, so that a number starting


can be anything between -1 and 1, and


can be anything between 0 and 1, etc.  It is then possible to guarantee
being able to output digits in a finite amount of time.  With a scheme
like this, the cases that blow up are ones you expect, like trying to
compute 1/0; there are ways around that, too.

As Jerzy Karczmarczuk mentioned, there is really extensive literature on
this.  It's beautiful stuff.

Part of my motivation for revising the numeric parts of the Prelude was
to make it possible to implement all this elegantly in Haskell.

--Dylan Thurston

Content-Type: application/pgp-signature
Content-Disposition: inline

Version: GnuPG v1.2.0 (GNU/Linux)