This is Pell’s equation: (1) where n is a positive integer that isn’t a perfect square. Only integer solutions for x and y are sought and if n is not a perfect square then there are infinitely many integer solutions. It can be shown that the convergents of the continued fraction (CF) for the square root of n contains a solution known as the Fundamental Solution (FS). In practice this fundamental solution is the first convergent that satisfies the equation under consideration. Once this solution is known then all other solutions can be calculated from a simple recurrence relationship. Read More

## Tag: algorithm

## 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 look at how to calculate the CF list format for the square root of an integer. 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 Read More

## Continued Fractions Continued.

It seems to me that continued fractions (CFs) are perhaps too advanced for ‘A’ levels and too elementary for a degree maths course and are perhaps undervalued or ignored in schools and universities? Since my last post about fractions I’ve looked a little more at CFs and found they have applications ranging from factorising large numbers to gear ratio calculations. And they’re really interesting when their layers are peeled away with a bit of Haskell. So, a bit of playing with numbers and a bit of Haskelling- what’s not to like? Let’s start with a fraction, any fraction – say Read More

## 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 Read More

## 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 Fibonacci Numbers Continued Fractions 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, Read More

## The Root of the Problem. Part 2.

In the previous post I discussed an algorithm for calculating the square root of a number. This short post will show an implementation in Haskell. I did one implementation using the State Monad but to be quite honest it was an impenetrable mess! I’m sure part of that was down to my embryonic Haskell skills but perhaps the State Monad was a bad fit for this problem? The implementation below uses a fold over a list of digit pairs and the start state for the fold is based on ‘the largest integer squared’ with subsequent calculations using ‘doubling’ – as Read More