Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Computation of Continued Fractions of irrational numbers

  1. Jun 21, 2011 #1
    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. jcsd
  3. Jun 22, 2011 #2
    Let [itex]\sqrt{2}[/itex] - 1 = [itex]\frac{1}{x}[/itex] for x > 0,

    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)]
     
  4. Jun 22, 2011 #3
    To explain the short notation of a Continued Fraction here are two samples:

    [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]
     
  5. Jun 23, 2011 #4
    Other Continued Fraction expansions are:

    [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)]
     
  6. Jun 24, 2011 #5
    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[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
     
  7. Jun 26, 2011 #6
    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[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
     
  8. Jun 27, 2011 #7
    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[itex]\sqrt{}c[/itex])/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.

    [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.
    62971363e3321d4371bd3c8fbed1ae6a.png

    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Computation of Continued Fractions of irrational numbers
  1. Irrational Numbers (Replies: 4)

  2. Irrational numbers (Replies: 9)

  3. Irrational Numbers (Replies: 73)

  4. Continued fractions (Replies: 3)

Loading...