Re: infinite (fractional) precision
G'day all. On Thu, Oct 10, 2002 at 11:50:39AM +0200, Jerzy Karczmarczuk wrote: > 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...) Already did it. It's not pretty, but I'll send you my implementation off-list. One thing I'd like to see is a lazy implementation of linear fractional transformations. The reason I'd like to see this is that it's easier to implement fixpoint-style computations (e.g. transcendental functions) using LFTs than using continued fractions. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: infinite (fractional) precision
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) > 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.0 + > 0.9 > ... 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 0.xx can be anything between -1 and 1, and 0.1x 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 msg02082/pgp0.pgp Description: PGP signature
Re: infinite (fractional) precision
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.0 +0.9
> >
> > The trouble is, as far as I know with a finite number of digits, the
> > answer might be 1.99937425 or it might be 2.00013565
> >
> > ...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
> [EMAIL PROTECTED]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: infinite (fractional) precision
Dear All, A really, really simple version in Haskell 1.2 has been available from ftp://ftp.cs.man.ac.uk/pub/arithmetic/Haskell/Era1/Era.hs for some considerable time. Of course the only reason for producing it was to show that the language designers didn't get it right. Take it from me, they never do [Is he being ironic here?]. In particular, although (<) and (==) are not computable functions over the computable reals, min and max are! Similarly, signum isn't computable, but abs is. The classes Ord and Num are a theoreticians nightmare. [For the mathematically sophisticated, the problem with these operations revolves around their continuity (in a weird numeric _and_ information theoretic sense) properties given the discrete nature of their range.] Then there's the rounding operation in Haskell 1.2. I must have wasted more hours fixing bugs caused by my naive understanding of _that_ operation than an other single misapprehension about a programming language construct in any langauge! In other files hanging off of http://www.cs.man.ac.uk/arch/dlester/exact.html you'll find a PVS development that shows that (most of) the implementation is correct. A paper on this theorem-proving work has been accepted for TCS, but I don't know whether it'll be published in my life time; and, I'm unsure about the ethics involved in puting up a copy of the paper on my website. However, a summary is: 4 bugs found, 3 only becoming manifest on doing the PVS work. I guess there's something to this formal methods lark after all. I'd planned to do a "Functional Pearl" about this library/package, but the theoretical development is embarassingly inelegant when compared to Richard Bird's classic functional pearls. If you think it'd be worth it, I'll see what I can do. I trust that this will save anyone wasting too much more time over this topic. David Lester. On Thu, 10 Oct 2002, 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) > 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.0 + > 0.9 > > The trouble is, as far as I know with a finite number of digits, the > answer might be > > 1.99937425 > > or it might be > > 2.00013565 > > ...so I can't actually generate any digits at all. So I can't even make > the type an instance of my Additive class. Not very useful... > > ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: infinite (fractional) precision
Ashley Yakeley <[EMAIL PROTECTED]> writes: > 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) > numbers, but because I couldn't properly make the type an instance of Eq, instance Eq InfPoint where x (==) y == compareToPrecision epsilon x y where epsilon = unsafePerformIO ... A bit (perhaps not just a bit either) ugly, but comparable to using a fixed point, no? > 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.0 + > 0.9 Could it be represented as data InfPoint = IP Integer FractionalPart data FractionalPart = FP Word8 | Repeat FractionalPart Thus: 1.00.. -> IP 1 (Repeat (FP 0)) 0.99.. -> IP 0 (Repeat (FP 9)) where the latter could be normalized to the former? Okay, you still get the problem comparing sqrt 2 == sqrt (sqrt 4) But wait a second: > The trouble is, as far as I know with a finite number of digits, the > answer might be > 1.99937425 > or it might be > 2.00013565 > ...so I can't actually generate any digits at all. But if you want to calcualte the sum for a finite number of digits, do you really care if you calculate it as 1.999..9 or 2.000..0 ? -kzm -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: infinite (fractional) precision
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.0 +0.9
>
> The trouble is, as far as I know with a finite number of digits, the
> answer might be 1.99937425 or it might be 2.00013565
>
> ...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
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: infinite (fractional) precision
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) 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.0 + 0.9 The trouble is, as far as I know with a finite number of digits, the answer might be 1.99937425 or it might be 2.00013565 ...so I can't actually generate any digits at all. So I can't even make the type an instance of my Additive class. Not very useful... -- Ashley Yakeley, Seattle WA ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: infinite (fractional) precision
Ketil Z. Malde wrote: > It seems one could easily (I'll get back to that in a moment) > calculate the fractional part of numbers lazily, generating the needed > precision, and nothing more. Does any such implementation exist in > Haskell? > > 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. > > So, if such implementations exist, how does one deal with these > issues? Is it indeed possible to make this useful in practice? Well, I implemented such a stuff for fun. Look here: http://users.info.unicaen.fr/~karczma/arpap/lazypi.ps.gz This shows how to implement Bailey-Borwein-Plouffe formula for PI, using lazy hexadec. fractions, and converting them to decimal. This is a crazy idea, with algorithms which are partly co-recursive, and partly recursive, borrowing the carry from the non-existing yet future. It could be done in a safer way, but I repeat that I did it for sheer joy. Perhaps one day I will return to it, unless somebody does it first. Jerzy Karczmarczuk ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: infinite (fractional) precision
On 10 Oct 2002 10:29:24 +0200 [EMAIL PROTECTED] (Ketil Z. Malde) wrote: > I realize it's probably far from trivial, e.g. comparing two equal > numbers could easily not terminate, you should compare into a given precision V. -- Fedeli alla linea, anche quando non c'è Quando l'imperatore è malato, quando muore,o è dubbioso, o è perplesso. Fedeli alla linea la linea non c'è. [CCCP] ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
infinite (fractional) precision
Hi I was just browsing around on comp.arch a bit, and there was this discussion about various ways to represent non-integer numeric values. It seems one could easily (I'll get back to that in a moment) calculate the fractional part of numbers lazily, generating the needed precision, and nothing more. Does any such implementation exist in Haskell? 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. So, if such implementations exist, how does one deal with these issues? Is it indeed possible to make this useful in practice? (And if it hasn't been implemented, would anybody be interested if I gave it a try?) -kzm -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
