Continued Fraction of a Square Root

Continued Fraction Expansion of a Square Root¶

MathForKids63 is the first video of a five part series on solving Pell's Equation.

These videos teach the Split / Flip / Rat procedure for finding the Continued Fraction Expansion of a square root by hand. For a natural number S (not a perfect square), we want to find the coefficients $a_i$ such that

\begin{equation} \sqrt{S} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cfrac{1}{a_4 + \cfrac{1}{a_5 +\cdots } } } } } \end{equation}

These coefficients will have a repeating pattern.

To generate the coefficients with Python, it is more convenient to implement the following iterative algorithm:

https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Algorithm

The following code snippet computes the expansion for $\sqrt{114}$

In [1]:

S=114

m = 0
d = 1
a0 = a = int(S**0.5)
C = []

done = False

while (done==False):
    m = a*d - m
    d = (S - m**2)/d
    a = int((a0 + m)/d)
    C.append(a)
    
    if (a==2*a0):
        done=True
        
        
print("Square Root",S,"= ",a0,",", C)

Square Root 114 =  10 , [1, 2, 10, 2, 1, 20]