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 "rediscovered" 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 (430501) 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 mooncrater 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 squareroot of 13 by a CFR. Apparently until
the end of the XVI^{th} 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 23 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: [*] x_{i} = a_{i} + 1/x_{i+1}, where i > 1,we
also assume all a_{i} are natural numbers.
A classical symbolic way used to describe such CFR is:
x_{0} = a_{0} + 1/a_{1} + 1/a_{2} + 1/a_{3} + .. + 1/a_{n+1}
and where A_{k} = a_{0} + 1/a_{1} + 1/a_{2} + 1/a_{3} + .. + 1/a_{k} represents
the kth approximation of the original equation [*].
The explicite way .. A_{0}=a_{0}/1 , A_{1}=(a_{0}a_{1}+1)/a_{1}, A_{2} = (a_{0}(a_{1}a_{2}+1)+a_{2})/(a_{1}a_{2}+1) suggests the recursion ..
P_{k} = a_{k}P_{k1} + P_{k2} and Q_{k} = a_{k}Q_{k1} + Q_{k2}. A trivial exercise shows A_{0}=P_{0}/Q_{0} and A_{1}=P_{1}/Q_{1}.
By mathematical induction we can prove easily that A_{k}=P_{k}/Q_{k}. We must be just aware that the Q_{k1},Q_{k2},P_{k1} and P_{k2}
are not dependent on the a_{k} and that in reality the a_{k} can represent the whole remaining fractiontree. From
the definition of D_{k} := P_{k}/Q_{k1}  P_{k1}/Q_{k} combined with the fact that D_{1} is 1,we deduct that D_{k} = (1)^{k1}.
This leads us to an interesting result:P_{k}/Q_{k}  P_{k1}/Q_{k1} = (1)^{k1}/Q_{k}Q_{k1}.
We obtain also P_{k}/Q_{k}  P_{k2}/Q_{k2} = (1)^{k}a_{k}/Q_{k}Q_{k2} from the original recursion definition. The last two equations
reveal two other interesting facts:

for all even k>1 the sequence P_{k}/Q_{k} is monotonic increasing and for odd k>2 monotonic decreasing

P_{j}/Q_{j} < P_{r}/Q_{r} for any odd r and any even j
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 a_{i}>0 and the last a_{k}>1)
A CFR we name infinite if we simply allow k>0 and a_{k}>0 .. and the CFR is converging if the sequence {A_{k}} is converging.
The proof for the convergence we have halfways done. The monotony of the even/odd A_{k}'s concludes:
A_{2k} < A _{2k+2} < A_{2k+3}< A_{2k+1}, which means the [P_{2k}/Q_{2k},P_{2k+1}/Q_{2k+1}]
represent nested intervals.
Now lets look at the Q_{k} .. Q_{0}=1,Q_{1}=a_{1},Q_{2}=a_{2}Q_{1}+Q_{0} >= 2,Q_{3}>=3 etc ..
So, assuming Q_{k} >= k .. we find that Q_{k+1} >= Q_{k} + Q_{k1} = k + (k1) = (k+1) + (k2) >= k+1 as k>3.
This implies that A_{2k+1}  A_{2k} = 1/Q_{2k}Q_{2k+1} < 1/4k^{2}, which means the nested intervals converge to 0.
This means the {A_{2k}} and the {A_{2k+1}} converge both to a limit l, or in other words:

for each e>0 there is a c_{1} > C_{1} so that A_{2k}l < e

for each e>0 there is a c_{2} > C_{2} so that A_{2k+1}l < e
And so for each e>0 and c > 1+ 2 max(C_{1},C_{2}) we will get A_{c}l < e, or in other words: {A_{k}} is coverging too.
One other interesting relation comes directly the differences A_{2k+1}  A_{2k} and A_{n+1}  A_{n} stated above:
P_{k+1}Q_{k}P_{k}Q_{k+1}=P_{k1}Q_{k}P_{k}Q_{k1} .. and so Q_{k}(P_{k+1}P_{k1}) = P_{k}(Q_{k+1}Q_{k1}) ie. P_{k}/Q_{k} = (P_{k+1}P_{k1})/(Q_{k+1}Q_{k1})
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: w_{0} < r < w_{0} + 1. w_{0} a natural number.
We define now a number r_{0} so that r = w_{0} + 1/r_{0}. Clearly r_{0} > 1. We apply the same idea with r_{0}:
w_{1} < r_{0} < w_{1} + 1 etc:
.. this process can never end, as r is not rational. The difference of the n+1 th and the nth approximation of r is
A_{n+1}  A_{n} = (1)^{n}/Q_{n}(a_{n+1}Q_{n}+Q_{n1}) >> r  A_{n} < 1/Q_{n}^{2} and so lim[A_{n}] = r.
The statement coming from this result is also kind of philosophical: r  P/Q < 1/Q^{2} .. which means, there is an
infinite number of rational "solutions" around an irrational number.
As 1^{st} 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.
13^{1/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 + b^{1/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 Ax^{2} + Bx + C = 0 (A,B,C whole numbers, and A not zero)
Just one word for caution: there is a danger of a numerical "stepup" effect, this means we cannot increase the
level too high without introducing an errorcorrection algorithm !! Thats an effect which can come quickly.
But now lets go a step further and approximate in k4 the squareroot 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:
P_{k}Q_{k1}  P_{k1}Q_{k} = D_{k} = (1)^{k1}, here two things have to be said:
a) The (1)^{k1} represents here the result of a (minimal) linear combination over P_{k} and Q_{k}, in other words
these two numbers are coprime.
b) If we multiply the equation above with (1)^{k1}, then Q_{k1}(1)^{k1} and P_{k1}(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/Q^{2}. 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:
x^{n}f_{k}^{(n)}(x_{k})+x^{n1}f_{k}^{(n1)}(x_{k})+ ... + xf_{k}'(x_{k})+f_{k}(x_{k})=0 the x_{k}(a natural number) will be a solution
and will therefore terminate the CFRbuilding process.
Lets look at the polynomial:x^{5}+2x^{4}4x^{3}+3x^{2}x6=0
A first draft solution in k4 would be for example:
o:();
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.636947e005 away
from the value 0.
Back to MAIN
©++ MILAN ONDRUS