• Back to MAIN

  • Chain Fractions (=CFRs) are sometimes also called "continued fractions" and they represent one other numerical
    method, completely different from the method described by Isaac Newton (4.Jan.1643 - 31.Mar.1727).
    The method of the CFRs represents in fact a very old part of mathematics and went forgotten for a long time.
    The CFR's were "re-discovered" only about 60 years ago.

    The Indian mathematician Aryabhata (476 - 550 aD) used a continued fraction to solve a linear indeterminate
    equation. The Chinese astronomer and mathematician Tsu Ch'ung Chi (430-501) approximated p = 3.14159.. by
    the fraction 355/113 which is correct to 6 decimal places. Chi's book went lost, so unfortunately it is not known how
    he actually arrived to this result. Chi calculated the time of the solstice with great precision. This lead modern
    astronomers to name a moon-crater after him.
    In Arab and Greek mathematical writings we find samples where continued fractions were used. The
    Italian mathematician Raphael Bombelli (1526 - 1573) expressed the square-root of 13 by a CFR. Apparently until
    the end of the XVIth century the CFR's were never investigated systematically.
    The English mathematician John Wallis (23.Nov.1616 - 28.Oct.1703) used the term "continued fraction"
    as the first, this was in the year 1653(or eventually 2-3 years later) - mentioned in his "Arithmetica infinitorum". John
    Wallis laid some of the basic groundwork for continued fractions in his other book "Opera Mathematica" issued 1695.
    In the year 1761 the German mathematician Johann Heinrich Lambert (26.Aug.1728 - 25.Sep.1777) proved
    the irrationality of p = 3.14159.. using CFR's. (in reality p is even transcendent)

    The simplest way to run into a CFR is by solving the equation system: [*] xi = ai + 1/xi+1, where i > -1,we
    also assume all ai are natural numbers.

    A classical symbolic way used to describe such CFR is:

    x0 = a0 + 1|/|a1 + 1|/|a2 + 1|/|a3 + .. + 1|/|an+1 and where Ak = a0 + 1|/|a1 + 1|/|a2 + 1|/|a3 + .. + 1|/|ak represents
    the k-th approximation of the original equation [*].

    The explicite way .. A0=a0/1 , A1=(a0a1+1)/a1, A2 = (a0(a1a2+1)+a2)/(a1a2+1) suggests the recursion ..

    Pk = akPk-1 + Pk-2 and Qk = akQk-1 + Qk-2. A trivial exercise shows A0=P0/Q0 and A1=P1/Q1.

    By mathematical induction we can prove easily that Ak=Pk/Qk. We must be just aware that the Qk-1,Qk-2,Pk-1 and Pk-2
    are not dependent on the ak and that in reality the ak can represent the whole remaining fraction-tree. From
    the definition of Dk := Pk/Qk-1 - Pk-1/Qk combined with the fact that D1 is 1,we deduct that Dk = (-1)k-1.
    This leads us to an interesting result:Pk/Qk - Pk-1/Qk-1 = (-1)k-1/QkQk-1.
    We obtain also Pk/Qk - Pk-2/Qk-2 = (-1)kak/QkQk-2 from the original recursion definition. The last two equations
    reveal two other interesting facts:
    Any rational number can undergo this treatment, in other words, each such number can be represented by the symbolic
    form mentioned above. (the representation is unique for normalized CFRs .. means if all ai>0 and the last ak>1)
    A CFR we name infinite if we simply allow k>0 and ak>0 .. and the CFR is converging if the sequence {Ak} is converging.
    The proof for the convergence we have halfways done. The monotony of the even/odd Ak's concludes:

    A2k < A 2k+2 < A2k+3< A2k+1, which means the [P2k/Q2k,P2k+1/Q2k+1] represent nested intervals.
    Now lets look at the Qk .. Q0=1,Q1=a1,Q2=a2Q1+Q0 >= 2,Q3>=3 etc ..
    So, assuming Qk >= k .. we find that Qk+1 >= Qk + Qk-1 = k + (k-1) = (k+1) + (k-2) >= k+1 as k>3.
    This implies that A2k+1 - A2k = 1/Q2kQ2k+1 < 1/4k2, which means the nested intervals converge to 0.

    This means the {A2k} and the {A2k+1} converge both to a limit l, or in other words: And so for each e>0 and c > 1+ 2 max(C1,C2) we will get |Ac-l| < e, or in other words: {Ak} is coverging too.

    One other interesting relation comes directly the differences A2k+1 - A2k and An+1 - An stated above:

    Pk+1Qk-PkQk+1=Pk-1Qk-PkQk-1 .. and so Qk(Pk+1-Pk-1) = Pk(Qk+1-Qk-1) ie. Pk/Qk = (Pk+1-Pk-1)/(Qk+1-Qk-1)

    In order to enter more practical grounds, let's now look at the irrational number r. It should not be difficult to put the
    next integer interval around it: w0 < r < w0 + 1. w0 a natural number.

    We define now a number r0 so that r = w0 + 1/r0. Clearly r0 > 1. We apply the same idea with r0: w1 < r0 < w1 + 1 etc:
    .. this process can never end, as r is not rational. The difference of the n+1 th and the n-th approximation of r is

    An+1 - An = (-1)n/Qn(an+1Qn+Qn-1) -->> |r - An| < 1/Qn2 and so lim[An] = r.

    The statement coming from this result is also kind of philosophical: |r - P/Q| < 1/Q2 .. which means, there is an
    infinite number of rational "solutions" around an irrational number.

    As 1st example we redo Raphael Bombelli's calculation in k4 .. which is:

    _ 20 {%x-_ x}\ sqrt 13

    ..and we get (3 1 1 1 1 6 1 1 1 1 6 1 1 1 1 6 1 1 1 1 6) which is the CFR 20 level's deep.
    131/2 = 3 + 1|/|1 + 1|/|1 + 1|/|1 + 1|/|1 + 1|/|6 + 1|/|1 + 1|/|1 + 1|/|1 + 1|/|1 + 1|/|6 + ..
    We see here something extraordinary happening .. we see a period in the CFR for an irrational number.

    And indeed, we could prove, that any number of the form (a + b1/2)/c (where a,b,c are whole numbers
    and c not a square) can be represented by a CFR with a specific periodicity and that the other way round, means
    that a CFR with such quality represents a quadratic irrationality. A quadratic irrationality is defined
    as an irrational solution of the equation Ax2 + Bx + C = 0 (A,B,C whole numbers, and A not zero)

    Just one word for caution: there is a danger of a numerical "step-up" effect, this means we cannot increase the
    level too high without introducing an error-correction algorithm !! Thats an effect which can come quickly.

    But now lets go a step further and approximate in k4 the square-root of 13 by fractions.

    {*x}''((4 3);(1 1)) {((y*c)+x 1),c:x 0}'\ 2 _ a

    and we get the nominators/denomitors (7 2;11 3;18 5;119 33;137 38;256 71;393 109;649 180;4287 1189;4936 1369;...)
    Lets take for example: 4936/1369 .. which is only 2*10-7 away from the correct value of [sqrt 13]

    Let's look a second time at the already shown relation:
    PkQk-1 - Pk-1Qk = Dk = (-1)k-1, here two things have to be said:

    a) The (-1)k-1 represents here the result of a (minimal) linear combination over Pk and Qk, in other words
    these two numbers are coprime.
    b) If we multiply the equation above with (-1)k-1, then Qk-1(-1)k-1 and Pk-1(-1)k represent
    a solution of the diophantine equation Ax + By = 1. (Diophantus of Alexandria(approx 214 - 280 ), Greek mathematician)

    So, let's choose as example: 97x + 115y = 36 .. and q gives us the chain fraction ..

    c:();{if[0W<>x 2;c,:u:floor (i:x 0)%j:x 1;.z.s@(j,mod[i;j],u)]} 97 115 0

    .. 0 1 5 2 1 1 3 0W (where the infinity can be ignored in the list c) .. and so we get by the k4 line:

    {*x}''((1 0);(1 1)) {((y*c)+x 1),c:x 0}'\ 2 _ -1 _ c

    (5 6;11 13;16 19;27 32;97 115) .. and where (27,32) "almost" represents the solution of the equation:

    It is: 97 * (-32*36) + 115 * (27 * 36) = 36 .. and so (-1152,972) are the only solutions.

    The CFR's are also representing the possibility to find an approximate value of a given polynomial with whole
    numbers as coefficients. The CFR's offer two advantages; one is that we know at each step how far we are from
    the real solution - that is based on our earlier findings:|r - P/Q| < 1/Q2. The second is if one
    solution is a rational number, then we get a finite CFR, which would mean, that within the step k of the iteration:

    xnfk(n)(xk)+xn-1fk(n-1)(xk)+ ... + xfk'(xk)+fk(xk)=0 the xk(a natural number) will be a solution
    and will therefore terminate the CFR-building process.

    Lets look at the polynomial:x5+2x4-4x3+3x2-x-6=0

    A first draft solution in k4 would be for example:

    p:1 2 -4 3 -1 -6f;

    do[6; S:min (2f*max -1 _ xexp[i;%|!#p]),1f+max i:abs p%*p;c:(|-1+-u),u:!_ S+1.5;
    o,:ze:*-1+c@(#r)-&~(*r) = r:|signum s:,/-1#{y+c*x}\ p;
    p:t**signum t:(1 _ r {y+ze*x}\\ p) ./: +(s;|s:!r:#p);]

    returning o with 1 2 1 1 1 9, which means the fraction 106/77 would be an approximation for the solution.
    The solution in this case is not rational but with the approximation we are only 5.636947e-005 away
    from the value 0.

  • Back to MAIN