infinite (fractional) precision
David Lester
dlester@cs.man.ac.uk
Thu, 10 Oct 2002 11:36:00 +0100 (BST)
On Thu, 10 Oct 2002, Jerzy Karczmarczuk wrote:
> 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.
I submitted a paper to JFP about lazy continued fractions in about 1997,
but got side-tracked into answering the reviewers' comments.
It _is_ possible to do continued fractions lazily, but proving that it's
correct involves a proof with several thousand cases. A discussion of
that proof can be found in "15th IEEE Symposium on Computer Arithmetic,
Vail 2001". I ought to get around to a journal publication someday.
David Lester.
> Anybody wants to do it with me? (Serious offers only...)
>
> Jerzy Karczmarczuk
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>