Parsers to Fractions to Square Roots!

The earlier post Fractions to Phi to Fibonacci! showed a simple structure for Continued Fractions (CF) and used a CF representation of the Golden Ratio to derive the terms of the Fibonacci Sequence. It also alluded to a particular notation to express a CF and here we will describe that notation, create a parser for it and calculate the square roots of some integers from their specific CFs and finally derive a general CF that can be used to find the square root of any integer.

 

CF List Notation

Essentially the CF is written as a list of ints like this [a0; a1, a2, a3…]. The first entry is followed by a ‘;’ and others by a ‘,’. The terms a1, a2, a3… taken together, are the ‘repeating’ terms and it is necessary to only write one ‘cycle’ of the repeating terms. For example root 2 as a CF is

and as a list this would be [1;2]

or

would be [1;1].
As for square roots of integers, here’s a list in CF list form. Again, for more details, please see

http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/cfINTRO.html#section6.3

√1 [ 1; ]
√2 [ 1; 2 ]
√3 [ 1; 1, 2 ]
√4 [ 2; ]
√5 [ 2; 4 ]
√6 [ 2; 2, 4 ]
√7 [ 2; 1, 1, 1, 4 ]
√8 [ 2; 1, 4 ]
√9 [ 3; ]
√10 [ 3; 6 ]

 

Haskell Abstraction

We can represent this list notation as a first Digit and then a list of the repeated Digit like this

really just some type synonyms and a FracStruc using record syntax.

Writing functions that will parse a string into a FracStruc is fairly straightforward I really quite enjoy this sort of thing with Haskell. So, using Megaparsec a few functions to do this are

I think most of this is fairly clear. The dropSpace uses the Applicative sequence actions where *> ignores the value of the first argument and <* ignores the value of the second argument, so dropping spaces ‘before and after’. The fracStrucP parser pull this together and we can test run it in GHCI like this:

and we see that the number 1 goes into first and the repeat part is a list with just 2 in it. A larger one:

and overall the parser is fairly forgiving of spurious spaces:

FracStruc has enough information to supply the values of the ‘a’s in a CF and we’re taking the ‘b’s to be fixed at 1. A function that takes a FracStruc and returns a function of Integer to Fraction is:

The returned function is specified by the lambda expression \n -> … such that if n is 0 then the value of first is returned. Otherwise the repeat list is indexed into in a circular fashion based on n and the length of the repeat list. We can now define this function:

The function frac takes a depth and a FracStruc and returns a Fraction. The ‘a’s are generated by genFa struc and the ‘b’s are fixed at 1. If there’s no repeating structure then the first from FracStruc is returned otherwise the contFrac (from the previous post) is called. We are now able to write a couple of functions to create a Fraction from a list:

And now we are able to write expression like these

As can be seen the result is in the Maybe monad and we can do this sort of thing evalFrac <$> (fracFromList 25 "[1;2]") to give Just 1.4142137

or we can write

so tying things back to the CF for root 2 and running in GHCI

we see the results in a monadic context. Or, if we wanted it in Maybe fraction form

And, just for phun – here’s the same phing for phis with the denom function fmapped over them.

Here is the list of the roots of 1..10 in CF list format

√1 [ 1; ]
√2 [ 1; 2 ]
√3 [ 1; 1, 2 ]
√4 [ 2; ]
√5 [ 2; 4 ]
√6 [ 2; 2, 4 ]
√7 [ 2; 1, 1, 1, 4 ]
√8 [ 2; 1, 4 ]
√9 [ 3; ]
√10 [ 3; 6 ]

and ignoring the √x chars we have a list like this [“[1;]”, “[1;2]”, “[1;1,2]”, “[2;]”, “[2;4]”, “[2;2,4]”, “[2;1,1,1,4]”, “[2;1,4]”, “[3;]”, “[3;6]”] and we can map evalFracM over it, to a depth of say 15, to give the square roots of 1..10 🙂

 

And finally

…it can be shown that

can be written as

clearly the CF list for this will be [1;2] and the function to generate the ‘b’s will simply be (x – 1). So a couple of simple function for this…

Here we use a ‘fixed’ FracStruc 1 [2] to create the ‘a’s. In the function root the function for the ‘b’s is a simple (n – 1). We can generate the roots of 1..10 by

fmap evalFrac [root n 10 | n <- [1..10]] which gives

[1.0,1.4142137,1.7320755,2.0000677,2.2340426,2.4503307,2.6476114,2.8319218,3.005865,3.1713445]

and is a lot simpler than the techniques discussed in the ‘Root of the Problem’ part 1 and part 2.

All the code is on Github.

Thanks for reading…!

 

Leave a Reply

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

ˆ Back To Top