# Computation of Continued Fractions of irrational numbers

1. Jun 21, 2011

### RamaWolf

In this field, computer algorithms may produce false continued fraction expansions because of
the limited accuracy in the floating point arithmetic used. Who knows more?

2. Jun 22, 2011

### RamaWolf

Let $\sqrt{2}$ - 1 = $\frac{1}{x}$ for x > 0,

or - equivalently - $\sqrt{2}$ + 1 = x, we get the well-known

identity x = 2 + $\frac{1}{x}$, from which we have

$\sqrt{2}$ - 1 = $\frac{1}{x}$ = $\frac{1}{2 + 1/x}$

Repeated replacement of x = 2 + $\frac{1}{x}$ in the denominator's 1/x

we get the Continued Fraction expression for $\sqrt{2}$ as

$\sqrt{2}$ = [1; 2, 2, 2, 2, 2, ,2 ,2 ...], or in short form [1; (2)]

3. Jun 22, 2011

### RamaWolf

To explain the short notation of a Continued Fraction here are two samples:

[b$_{0}$; b$_{1}$, b$_{2}$] = b$_{0}$+$\frac{1}{b_{1}+\frac{1}{b_{2}}}$

[b$_{0}$; b$_{1}$, b$_{2}$, b$_{3}$] = b$_{0}$+$\frac{1}{b_{1}+\frac{1}{b_{2}+\frac{1}{b_{3}}}}$

4. Jun 23, 2011

### RamaWolf

Other Continued Fraction expansions are:

$\sqrt{3}$ := [1; 1, 2, 1, 2, 1, 2, 1, 2, ...] or in short form : [1; (1, 2)]

$\sqrt{5}$ := [2; (4)] $\sqrt{6}$ := [2; (2, 4)] $\sqrt{7}$ := [2; (1, 1, 1, 4)]

$\sqrt{8}$ := [2; (1, 4)] $\sqrt{10}$ := [3; (6)] $\sqrt{11}$ := [3; (3, 6)]

$\sqrt{12}$ := [3; (2, 6)] $\sqrt{13}$ := [3; (1, 1, 1, 1, 6)] $\sqrt{14}$ := [3; (1, 2, 1, 6)]

$\sqrt{15}$ := [3; (1, 6)] $\sqrt{17}$ := [4; (8)] $\sqrt{18}$ := [4; (4, 8)]

5. Jun 24, 2011

### RamaWolf

The solution of Pell's equation is connected to the (periodic) expansion of a specific Continued Fraction by the following theorem due to Lagrange:

Theorem Let x$^{2}$ - N*y$^{2}$ = 1 for a non-square integer N,
let $\sqrt{N}$ have a periodic Continued Fraction expansion of length k,
and let $\frac{s}{t}$ be it's (k - 1)th convergent,
then (s, t) is a solution to the Pell's equation

As an example, we take N = 19 and we try to compute the Continued Fraction (CF) expansion
using different compiler's floating point accuracy:

SQRT(19) = 0.43588 * 10$^{1}$ -> CF = [4; 2,1,3,1,2,3,2,2,3,2,6,1,7,...]

SQRT(19) = 0.4358898 * 10$^{1}$ -> CF = [4; 2,1,3,1,2,8,3,1,2,52,2,3.....]

SQRT(19) = 0.435889894 * 10$^{1}$ -> CF = [4; 2,1,3,1,2,8,2,1,3,1,3,396,....]

SQRT(19) = 0.43588989435 * 10$^{1}$ -> CF = [4; 2,1,3,1,2,8,2,1,3,1,2,7,1,5,..]

with no periodicity; only with 13 digits accuracy (or more) we finally have

SQRT(19) = 0.4358898943540 * 10$^{1}$ -> CF = [4; (2,1,3,1,2,8)]

The period length is 6, and for the computation of the 5-th CF convergent we use
the function Inv(q), which reverses numerator and denominator of a rational fraction:

C$_{5}$($\sqrt{19}$):=4+Inv(2+Inv(1+Inv(3+Inv(1+$\frac{1}{2}$))))) := $\frac{170}{39}$

and x=170, y= 39 is a solution to x$^{2}$ - 19*y$^{2}$ = 1

6. Jun 26, 2011

### RamaWolf

To avois any issues with the mssing accuracy of the floation point arithmetic, it is suggested
to use accurate 'rational arittmetic' to evaluate the Continued Fraction expansion of a
integer N, not a perfect square.

To this end we use the following

Theorem on rational convergents of a square root: Let N be an integer, not a perfect square,
c$_{0}$ := 1/1 and define recursively, c$_{i+1}$ := $\frac{c_{i}+N/c_{i}}{2}$, we have $\underbrace{lim}_{i->\infty}$ c$_{i}$ -> $\sqrt{N}$

As an exampel, the rational convergents of $\sqrt{19}$ are:

c$_{1}$ := 10/1, c$_{2}$ := 119/20, c$_{3}$ := 21761/4760, c$_{4}$ := 904035521/207164720
c$_{5}$ := 1632707426270631041 / 374568531156038240,
c$_{6}$ := 5331463645914715901021239526856398081 / 1223121644931491741401139604654015680

Using c$_{6}$ the CF expansion of $\sqrt{19}$ was compute as [4; 2,1,3,1,2,8,2,1,3,1,2,8,2,1,...], establishing this expansion as [4;(2,1,3,1,2,8)]

The rational arithmetc was done using the 'Q' package of my long-integer arithmetic VAR16

7. Jun 27, 2011

### KevB

Any root of a whole number, or root of a rational for that mater will have a repeated continued fraction as you described. That's true for any quadratic surd ( http://en.wikipedia.org/wiki/Quadratic_surd ). The converse is also true, so if it has repeated coefficients it's of the form (a+b$\sqrt{}c$)/d for some integer values a,b,c and d.

The continued fraction representations for square roots of integers also have an interesting property that the repeat sequence is a palindrome (same forward as backward). The last term of the repeated sequence is always twice the integer part of the square root.

$\sqrt{46}$ = CFS([6L, 1L, 3L, 1, 1, 2L, 6L, 2L, 1, 1L, 3L, 1L, 12L],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0L])
$\sqrt{71}$ = CFS([8L, 2L, 2L, 1, 7L, 1, 2L, 2L, 16L],[0, 0, 0, 0, 0, 0, 0, 0L])'
$\sqrt{94}$ = CFS([9L, 1L, 2L, 3L, 1, 1, 5L, 1, 8L, 1, 5L, 1, 1L, 3L, 2L, 1, 18L],16)

Other mathematical constants also have interesting representations in continued fractions.

For example e = [ 2; 1, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1,8, ...] = CFS([2,1,2,1],[0,2,0] = CFS([1,0,1],[0,2,0])
$\sqrt{e}$ = [ 1; 1, 1, 1, 5, 1, 1, 9, 1, 1, 13, 1,...] = CFS([1,1,1],[0,4,0])
$\sqrt[n]{e}$ = [ 1; (n-1), 1, 1, (3n-1), 1, 1, (5n-1), ...] = CFS([1, (n-1), 1],[0, 2*n,0])

While $\pi$ does not have a simple 'simple continued fraction' form it does have several nice 'generalized continued fraction' forms.

There are some nice algorithms that deal with calculations using continued fractions. Check out Bill Gosper's algorithm in the unpublished Hakmem http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html .

Nothing says accuracy like exact arithmetic.

Last edited: Jun 27, 2011