Fractions to Phi to Fibonacci!

Oh no, not another Haskell way of calculating Fibonacci numbers! Well, yes but done perhaps slightly differently.
This post brings together

The Golden Ratio (Phi)

“…two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities.”

This ratio appears often mathematics and in nature, perhaps almost as pervasive as pi. And there is the Golden Rectangle, a 2-D extension of the Golden Ratio, often used in art because of its intrinsically appealing properties.

Fibonacci Numbers

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,… ‘Nuff said.

Continued Fractions

Are like this, fractions where the denominator is also a fraction and so on…

The idea in this post is to create a Haskell representation of fractions but in particular have that representation handle continued fractions. Once we can do that then we can create a continued fraction for the Golden Ratio, which is this:

and then, if the continued fraction above is ‘flattened’ into a list of intermediate fractions, the denominators of those intermediate fractions are the terms of the Fibonacci series! Which I think is quite stunning.

For details see section 11 in this link: The Convergents of Phi’s CF are Ratios of Fibonacci Numbers!

 

A Little Bit of Haskell

A fraction is a numerator ‘over’ a denominator and we’ll also consider a whole number to be a fraction with an implicit denominator of 1.
Furthermore, if we are to have continued fractions then the denominator must, optionally, be a fraction too. Here’s a couple of type synonyms and an algebraic data type to express these ideas.

This will allow us to create a simple fraction like, for example, Numbr 4 which is 4/1 or using the F type constructor F 7 (Numbr 8). A continued fraction could be something like F 7 (F 6 (F 11 (Numbr 23))) which could be have been continued indefinitely, which is quite cool!

Next we need a sensible way of showing fractions – we do this by making Fraction an instance of the Show type class like this

This is fairly simple pattern matching on the show function. The final pattern is slightly more complex as it handles the condition where a fraction may have another fraction as its denominator and so it calls show again recursively.

If we make Fraction an instance of the Num typeclass then we can, with suitable definitions, use operators +, -, * on Fractions. And, if we make Fraction an instance of Haskell’s Fractional typeclass we can use the division, /, operator. I think the code is fairly self explanatory so I’ll add it all here and then describe some of the more important parts.

The functions mul, add, sub and divid are all fairly simple and are really how you would expect multiplication, addition, subtraction and division of fractions to be done and they work on continued fractions by calling simplify before applying the operation.
The function contFrac is the core of what we are doing and it’s really quite a simple recursive function. It take two ‘generator’ functions that supply the a and b values in this image:

and the depth parameter determines how many times it recurses. So with a pair of suitable generator functions many (maybe all) continued fractions can be generated. For example the square root of 2 is

and so we have

Trying this out in GHCi to a depth of 5 we get

To a depth of 10 we get

We can also get the terms for each value of depth like this

Or, in fraction form:

The continued fraction for phi is really simple – the ‘a‘ s and ‘b‘ s are all 1.

Calculating to a depth of 100 we have

which is quite accurate!
Getting the terms out we have…

If we now map denom (or num) over phis we get the terms of the Fibonacci series! 🙂

or slightly larger…

λ-> map denom phis
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040]

which was the purpose of this post.

 

Concluding Notes

What I’ve written here has only touched the surface of continued fractions. I hope that future posts will

  • explore an alternative to foldr when resolving a continued fraction.
  • create a parser that will generate continued fractions from standard notation for continued fractions
  • extend the type beyond fractions using integers to fractions with complex numbers

This website is a mine of wonderfully explained ideas about fractions and is well worth a look. It explains in a clear and detailed way many properties of continued fractions.

You can find this Haskell code in GitHub.

Thanks for reading…!

 

 

Leave a Reply

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

ˆ Back To Top