[Haskell-cafe] strictness and the simple continued fraction

[Dylan Thurston]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20041012/8a4c2963/attachment.bin