infinite (fractional) precision

[David Lester]

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
>