Continued Fractions in Haskell

gbrown_ | 96 points

Continued fractions are quite awesome. Gospers monograph, which is also mentioned in the article, is quite readable: https://perl.plover.com/classes/cftalk/INFO/gosper.txt

One thing to watch out for is that when you compute floor(sqrt(2) * sqrt(2)), the computation will never finish. The reason is that continued fractions only compute approximations, so the approximation will only tell you that the result is very close to 2, but it might still be slightly above or below 2. That is, unless you implement some logic to deal with repeating coefficients, but then you will have the same problem with 1/pi times pi, for example.

rustybolt | 3 years ago

The sequence is certainly not useless?? This is how you construct real numbers. It is what is called a completion. A real number is a sequence of rationals. You take the space of all sequences of rationals and then quotient out by an ideal of sequences which converge in a sense. I think about the limit object by thinking to some finite depth (truncation). The existence of a limit object is because there are arrows between the different finite steps. A continued fraction is just a nice representation, it’s the same thing.

fennecs | 3 years ago

The actual title did not fit within the character limits and I couldn't chop it down without really changing it, so I've submitted this with the title of the author's earlier version.

gbrown_ | 3 years ago

I never knew about continued fractions.

Impressive the very simple representations of sqrt of 2, sqrt of 3 and sqrt of 5.

BoiledCabbage | 3 years ago

So how fast does it go?

yarg | 3 years ago

Haskell is this kind of language which makes hard things easy when you are smart and easy things hard for everyone else.

jhoechtl | 3 years ago