Computation of Continued Fractions of irrational numbers

[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?

 

[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)]

 

[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}}}}

 

[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)]

 

[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

 

[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

 

[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.