chain fractions

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 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 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: [*] 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₀ = a₀ + 1|/|a₁ + 1|/|a₂ + 1|/|a₃ + .. + 1|/|a_n+1 and where A_k = a₀ + 1|/|a₁ + 1|/|a₂ + 1|/|a₃ + .. + 1|/|a_k represents
the k-th approximation of the original equation [*].

The explicite way .. A₀=a₀/1 , A₁=(a₀a₁+1)/a₁, A₂ = (a₀(a₁a₂+1)+a₂)/(a₁a₂+1) suggests the recursion ..

P_k = a_kP_k-1 + P_k-2 and Q_k = a_kQ_k-1 + Q_k-2. A trivial exercise shows A₀=P₀/Q₀ and A₁=P₁/Q₁.

By mathematical induction we can prove easily that A_k=P_k/Q_k. We must be just aware that the Q_k-1,Q_k-2,P_k-1 and P_k-2
are not dependent on the a_k and that in reality the a_k can represent the whole remaining fraction-tree. From
the definition of D_k := P_k/Q_k-1 - P_k-1/Q_k combined with the fact that D₁ is 1,we deduct that D_k = (-1)^k-1.
This leads us to an interesting result:P_k/Q_k - P_k-1/Q_k-1 = (-1)^k-1/Q_kQ_k-1.
We obtain also P_k/Q_k - P_k-2/Q_k-2 = (-1)^ka_k/Q_kQ_k-2 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₀=1,Q₁=a₁,Q₂=a₂Q₁+Q₀ >= 2,Q₃>=3 etc ..
So, assuming Q_k >= k .. we find that Q_k+1 >= Q_k + Q_k-1 = k + (k-1) = (k+1) + (k-2) >= k+1 as k>3.
This implies that A_2k+1 - A_2k = 1/Q_2kQ_2k+1 < 1/4k², 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₁ > C₁ so that |A_2k-l| < e

for each e>0 there is a c₂ > C₂ so that |A_2k+1-l| < e

And so for each e>0 and c > 1+ 2 max(C₁,C₂) 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+1Q_k-P_kQ_k+1=P_k-1Q_k-P_kQ_k-1 .. and so Q_k(P_k+1-P_k-1) = P_k(Q_k+1-Q_k-1) ie. P_k/Q_k = (P_k+1-P_k-1)/(Q_k+1-Q_k-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: w₀ < r < w₀ + 1. w₀ a natural number.

We define now a number r₀ so that r = w₀ + 1/r₀. Clearly r₀ > 1. We apply the same idea with r₀: w₁ < r₀ < w₁ + 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

A_n+1 - A_n = (-1)ⁿ/Q_n(a_n+1Q_n+Q_n-1) -->> |r - A_n| < 1/Q_n² and so lim[A_n] = r.

The statement coming from this result is also kind of philosophical: |r - P/Q| < 1/Q² .. 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² + 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:
P_kQ_k-1 - P_k-1Q_k = D_k = (-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 P_k and Q_k, in other words
these two numbers are coprime.
b) If we multiply the equation above with (-1)^k-1, then Q_k-1(-1)^k-1 and P_k-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/Q². 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ⁿf_k⁽ⁿ⁾(x_k)+x^n-1f_k^(n-1)(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 CFR-building process.

Lets look at the polynomial:x⁵+2x⁴-4x³+3x²-x-6=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.636947e-005 away
from the value 0.

Back to MAIN