Re: [Haskell-cafe] strictness and the simple continued fraction
On Mon, Oct 11, 2004 at 09:53:16PM -0400, Scott Turner wrote: > Evenutally I realized that calculating with lazy lists is not as > smooth as you might expect. For example, the square root of 2 has a > simple representation as a lazy continued fraction, but if you > multiply the square root of 2 by itself, your result lazy list will > never get anywhere. The calculation will keep trying to determine > whether or not the result is less than 2, this being necessary to > find the first number in the representation. But every finite prefix > of the square root of 2 leaves uncertainty both below and above, so > the determination will never be made. Right, one way to think about this problem is that the representations by continued fractions are unique, so there's no way to compute the prefix of a representation for something right on the boundary. Representing numbers by lazy strings of, say, decimal digits has the same problem. There are known solutions, but they lack the elegance of continued fraction representations. You fundamentally have to have non-unique representations, and that causes some other problems. One popular version is to use base 2 with digits -1, 0, and +1. Simon Peyton-Jones already posted the references. These methods appear to lose out in practice to using a large fixed precision and interval arithmetic, increasing the precision and recomputing as necessary. Peace, Dylan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] strictness and the simple continued fraction
On Tue, Oct 12, 2004 at 08:48:27AM +0100, Simon Peyton-Jones wrote: > If you are interested in arbitrary precision arithmetic using continued > fractions, you may want to check out the work of David Lester. And > Peter Potts et al. Just type "exact real arithmetic" into Google. That's where I got the ContFrac.hs I started with, though I used a different search string. =) -- wli ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] strictness and the simple continued fraction
If you are interested in arbitrary precision arithmetic using continued fractions, you may want to check out the work of David Lester. And Peter Potts et al. Just type "exact real arithmetic" into Google. Simon | -Original Message- | From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of | William Lee Irwin III | Sent: 12 October 2004 04:53 | To: Scott Turner | Cc: [EMAIL PROTECTED] | Subject: Re: [Haskell-cafe] strictness and the simple continued fraction | | On Mon, Oct 11, 2004 at 09:53:16PM -0400, Scott Turner wrote: | > I tried using continued fractions in a "spiffy lazy list" implementation a | > while ago. Never got them working as well as expected. | > Evenutally I realized that calculating with lazy lists is not as | > smooth as you might expect. | > For example, the square root of 2 has a simple representation | > as a lazy continued fraction, but if you multiply the square root of 2 by | > itself, your result lazy list will never get anywhere. The calculation will | > keep trying to determine whether or not the result is less than 2, this being | > necessary to find the first number in the representation. But every finite | > prefix of the square root of 2 leaves uncertainty both below and above, so | > the determination will never be made. | > Your problems may have some other basis, but I hope this helps. | | I hit that one, too. That's nasty enough it may be best to give up on | the infinite case, at least. I can't think of a way to salvage all this. | | | -- wli | ___ | 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: [Haskell-cafe] strictness and the simple continued fraction
On Mon, Oct 11, 2004 at 09:53:16PM -0400, Scott Turner wrote: > I tried using continued fractions in a "spiffy lazy list" implementation a > while ago. Never got them working as well as expected. > Evenutally I realized that calculating with lazy lists is not as > smooth as you might expect. > For example, the square root of 2 has a simple representation > as a lazy continued fraction, but if you multiply the square root of 2 by > itself, your result lazy list will never get anywhere. The calculation will > keep trying to determine whether or not the result is less than 2, this being > necessary to find the first number in the representation. But every finite > prefix of the square root of 2 leaves uncertainty both below and above, so > the determination will never be made. > Your problems may have some other basis, but I hope this helps. I hit that one, too. That's nasty enough it may be best to give up on the infinite case, at least. I can't think of a way to salvage all this. -- wli ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] strictness and the simple continued fraction
On 2004 October 09 Saturday 15:33, William Lee Irwin III wrote: > So, I discovered that simple continued fractions are supposed to be > spiffy lazy lists and thought I'd bang out some continued fraction code. > But then I discovered ContFrac.hs and couldn't really better it. Of > course, I went about trying to actually do things relying on their > laziness, and discovered they weren't as lazy as I hoped they'd be. I tried using continued fractions in a "spiffy lazy list" implementation a while ago. Never got them working as well as expected. Evenutally I realized that calculating with lazy lists is not as smooth as you might expect. For example, the square root of 2 has a simple representation as a lazy continued fraction, but if you multiply the square root of 2 by itself, your result lazy list will never get anywhere. The calculation will keep trying to determine whether or not the result is less than 2, this being necessary to find the first number in the representation. But every finite prefix of the square root of 2 leaves uncertainty both below and above, so the determination will never be made. Your problems may have some other basis, but I hope this helps. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] strictness and the simple continued fraction
On Sat, Oct 09, 2004 at 12:33:53PM -0700, William Lee Irwin III wrote: >> So, I discovered that simple continued fractions are supposed to be >> spiffy lazy lists and thought I'd bang out some continued fraction code. >> But then I discovered ContFrac.hs and couldn't really better it. Of >> course, I went about trying to actually do things relying on their >> laziness, and discovered they weren't as lazy as I hoped they'd be. >> Simple uses of approximations at the ghci command line such as: On Sat, Oct 09, 2004 at 12:39:44PM -0700, William Lee Irwin III wrote: > Of course, I instantly discover the bug once I publicly embarrass myself. > Please disregard. Gaffe #2, fixing compare didn't actually fix it. Bombs away... -- wli ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] strictness and the simple continued fraction
On Sat, Oct 09, 2004 at 12:33:53PM -0700, William Lee Irwin III wrote: > So, I discovered that simple continued fractions are supposed to be > spiffy lazy lists and thought I'd bang out some continued fraction code. > But then I discovered ContFrac.hs and couldn't really better it. Of > course, I went about trying to actually do things relying on their > laziness, and discovered they weren't as lazy as I hoped they'd be. > Simple uses of approximations at the ghci command line such as: Of course, I instantly discover the bug once I publicly embarrass myself. Please disregard. -- wli ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] strictness and the simple continued fraction
So, I discovered that simple continued fractions are supposed to be spiffy lazy lists and thought I'd bang out some continued fraction code. But then I discovered ContFrac.hs and couldn't really better it. Of course, I went about trying to actually do things relying on their laziness, and discovered they weren't as lazy as I hoped they'd be. Simple uses of approximations at the ghci command line such as: instance Ord ContFrac where (ContFrac (x:xs)) `compare` (ContFrac (y:ys)) = case x `compare` y of LT -> LT GT -> GT EQ -> (ContFrac ys) `compare` (ContFrac xs) (ContFrac []) `compare` cf = case cf of ContFrac (x:_) -> 0 `compare` x ContFrac [] -> EQ cf `compare` (ContFrac []) = case cf of ContFrac (x:_) -> x `compare` 0 ContFrac [] -> EQ x = expCF (1/2) where expCF x | x < 0 = recip . expCF $ negate x | x == 0 = 1 | x == 1 = let ContFrac es = ecf in ContFrac (take 100 es) | otherwise = case x of ContFrac [y] -> (expCF 1)^y ContFrac (y:ys) -> if y /= 0 then ((expCF 1)^y) *(expCF (ContFrac (0:ys))) else (1+x+x^2/2+x^3/6+x^4/24+x^5/120) ContFrac [] -> expCF 0 where the instance was added to ContFrac.hs seems to fail to terminate, where manually reducing things a bit appears to restore termination. So, what hit me? -- wli ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
