Function That Computes the Continued Fraction Expansion Matlab
Computation of Continued Fractions of irrational numbers
- Thread starter RamaWolf
- Start date
the limited accuracy in the floating point arithmetic used. Who knows more?
Answers and Replies
or - equivalently - [itex]\sqrt{2}[/itex] + 1 = x, we get the well-known
identity x = 2 + [itex]\frac{1}{x}[/itex], from which we have
[itex]\sqrt{2}[/itex] - 1 = [itex]\frac{1}{x}[/itex] = [itex]\frac{1}{2 + 1/x}[/itex]
Repeated replacement of x = 2 + [itex]\frac{1}{x}[/itex] in the denominator's 1/x
we get the Continued Fraction expression for [itex]\sqrt{2}[/itex] as
[itex]\sqrt{2}[/itex] = [1; 2, 2, 2, 2, 2, ,2 ,2 ...], or in short form [1; (2)]
[b[itex]_{0}[/itex]; b[itex]_{1}[/itex], b[itex]_{2}[/itex]] = b[itex]_{0}[/itex]+[itex]\frac{1}{b_{1}+\frac{1}{b_{2}}}[/itex]
[b[itex]_{0}[/itex]; b[itex]_{1}[/itex], b[itex]_{2}[/itex], b[itex]_{3}[/itex]] = b[itex]_{0}[/itex]+[itex]\frac{1}{b_{1}+\frac{1}{b_{2}+\frac{1}{b_{3}}}}[/itex]
[itex]\sqrt{3}[/itex] := [1; 1, 2, 1, 2, 1, 2, 1, 2, ...] or in short form : [1; (1, 2)]
[itex]\sqrt{5}[/itex] := [2; (4)] [itex]\sqrt{6}[/itex] := [2; (2, 4)] [itex]\sqrt{7}[/itex] := [2; (1, 1, 1, 4)]
[itex]\sqrt{8}[/itex] := [2; (1, 4)] [itex]\sqrt{10}[/itex] := [3; (6)] [itex]\sqrt{11}[/itex] := [3; (3, 6)]
[itex]\sqrt{12}[/itex] := [3; (2, 6)] [itex]\sqrt{13}[/itex] := [3; (1, 1, 1, 1, 6)] [itex]\sqrt{14}[/itex] := [3; (1, 2, 1, 6)]
[itex]\sqrt{15}[/itex] := [3; (1, 6)] [itex]\sqrt{17}[/itex] := [4; (8)] [itex]\sqrt{18}[/itex] := [4; (4, 8)]
Theorem Let x[itex]^{2}[/itex] - N*y[itex]^{2}[/itex] = 1 for a non-square integer N,
let [itex]\sqrt{N}[/itex] have a periodic Continued Fraction expansion of length k,
and let [itex]\frac{s}{t}[/itex] 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[itex]^{1}[/itex] -> CF = [4; 2,1,3,1,2,3,2,2,3,2,6,1,7,...]
SQRT(19) = 0.4358898 * 10[itex]^{1}[/itex] -> CF = [4; 2,1,3,1,2,8,3,1,2,52,2,3.....]
SQRT(19) = 0.435889894 * 10[itex]^{1}[/itex] -> CF = [4; 2,1,3,1,2,8,2,1,3,1,3,396,....]
SQRT(19) = 0.43588989435 * 10[itex]^{1}[/itex] -> 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[itex]^{1}[/itex] -> 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[itex]_{5}[/itex]([itex]\sqrt{19}[/itex]):=4+Inv(2+Inv(1+Inv(3+Inv(1+[itex]\frac{1}{2}[/itex]))))) := [itex]\frac{170}{39}[/itex]
and x=170, y= 39 is a solution to x[itex]^{2}[/itex] - 19*y[itex]^{2}[/itex] = 1
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[itex]_{0}[/itex] := 1/1 and define recursively, c[itex]_{i+1}[/itex] := [itex]\frac{c_{i}+N/c_{i}}{2}[/itex], we have [itex]\underbrace{lim}_{i->\infty}[/itex] c[itex]_{i}[/itex] -> [itex]\sqrt{N}[/itex]
As an exampel, the rational convergents of [itex]\sqrt{19}[/itex] are:
c[itex]_{1}[/itex] := 10/1, c[itex]_{2}[/itex] := 119/20, c[itex]_{3}[/itex] := 21761/4760, c[itex]_{4}[/itex] := 904035521/207164720
c[itex]_{5}[/itex] := 1632707426270631041 / 374568531156038240,
c[itex]_{6}[/itex] := 5331463645914715901021239526856398081 / 1223121644931491741401139604654015680
Using c[itex]_{6}[/itex] the CF expansion of [itex]\sqrt{19}[/itex] 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
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.
[itex]\sqrt{46}[/itex] = 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])
[itex]\sqrt{71}[/itex] = CFS([8L, 2L, 2L, 1, 7L, 1, 2L, 2L, 16L],[0, 0, 0, 0, 0, 0, 0, 0L])'
[itex]\sqrt{94}[/itex] = 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])
[itex]\sqrt{e}[/itex] = [ 1; 1, 1, 1, 5, 1, 1, 9, 1, 1, 13, 1,...] = CFS([1,1,1],[0,4,0])
[itex]\sqrt[n]{e}[/itex] = [ 1; (n-1), 1, 1, (3n-1), 1, 1, (5n-1), ...] = CFS([1, (n-1), 1],[0, 2*n,0])
While [itex]\pi[/itex] 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.
Suggested for: Computation of Continued Fractions of irrational numbers
- Last Post
- Last Post
- Last Post
- Last Post
- Last Post
- Last Post
- Last Post
- Last Post
- Last Post
- Last Post
Source: https://www.physicsforums.com/threads/computation-of-continued-fractions-of-irrational-numbers.508611/
0 Response to "Function That Computes the Continued Fraction Expansion Matlab"
Post a Comment