More Continued Fractions Continued.

In the post Parsers to Fractions to Square Roots! we looked at continued fractions (CFs) expressed in list format and used that format to calculate the square root of integers. The technique didn’t really explore an effective way of generating the list form for a CF. In this short post we’ll

  1. look at how to calculate the CF list format for the square root of an integer.
  2. Then, from the list, calculate the convergents, each of which gives a better and better value for the square root. (The details of convergents have been covered in Continued Fractions Continued.)

With a few helper functions, along with items 1 and 2, we will be able to write something like
take 20 . map evalFrac . convergents . cfListSqrtN $ 234 which will give the first twenty approximations to the square root of 234.

Wikepedia has a very good reference and explanation of the iterative formulae for the CF list of an integer. An implementation in Haskell is shown below.

The above code is slightly different to the referenced formulae in that it handles the degenerate case of the input being a perfect square.
Also the term a02 = a0 * 2 is included because

  • It can be shown that all CF lists for the square roots of integers are infinite and periodic.
  • The period or cycle ends when the current term equals twice the first term

so cfListSqrtN :: Integer -> CFList – which will provide an infinite list – can be modified to produce a finite implicitly periodic list. The modification involves using takeWhile like this (note that CFList is just a synonym for [Integer] )

Both functions are essentially the same – it’s just a matter of where the ‘no longer taking happens’ . e.g.

As can be seen the list repeats on twice the first term i.e at 16. Which to use? It’s just a question of whether you want a finite but implicitly infinite list or an explicitly infinite list. In what follows I’ll use the explicit form and just take however many terms are needed.

My post Continued Fractions Continued described how to generate the convergents from a CFList – and I’ve copied it in here.

So playing around with these functions…taking the first 10 convergents of the CF list for the root of 101 we have

We have the first approximation of root 101 is 10/1, the second being 201/20 and so on. Quite quickly developing into the ratio of fairly large Integers. So just for fun if we do

which will give the 1000th convergent we get two very, very large Integers 🙂

and these are around 1300 digits each 🙂

Being more realistic we can evaluate the first 20 or so convergents by mapping evalFrac over the list like this

which quite quickly converges to an accurate value – compare with Haskells sqrt function which gives 10.04987562112089

If we, for the sake of argument, say that for a given integer the 10th convergent is the value we are accepting as the square root of the integer then we can compare each convergent to this value and see how they change and notice, quite interestingly, that the difference between the value and the convergent alternates above and below the value. To do this we use this simple function

and applying it

As can be seen the differences (second term of tuple) alternate +ve and -ve.

I had originally planned this post to be about Pells Equation and its solution in Haskell using CFs and convergents. However, central to solving Pell is the expression of the square root of an integer as a CF. And, given my previous posts about calculating square roots I thought this technique warranted its own small post. So, the next post in this series on CFs will explore Pells equation and provide a neat Haskell implementation of its solution. All this code is in GitHub.

 

Thanks for reading…!

 

 

 

 

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *

ˆ Back To Top