Let a0 be the greatest integer ≤ r, and let c0 = a0. Let e0 = r-a0, the error in selecting a0.
Once a1 is selected, c1 will equal a0 + 1/a1. Let a1 be as large as it can be, such that c1 is not less than r. Note that a1 is at least 1.
Solve for a1 and get a1 = int(1/e0). Let e1 be the remainder, the error, when selecting a1. In other words, e1 = 1/e0 - a1.
Notice the alternation. To start, c0 ≤ r, then c1 ≥ r. This will continue with c2 ≤ r, and so on.
Use a2 to "adjust" a1. Specifically, the reciprocal of a2 is added to a1, just as the reciprocal of a1 was added to a0. Thus c2 = a0+1/(a1+1/a2). If a2 = 1 then a1 is increased by 1, and that puts us below r. So there is some largest integer a2, greater than or equal to 1, that keeps c2 less than or equal to r.
Solve for a2 and find a2 = int(1/e1). Set e2 = 1/e1 - a2.
These definitions continue forever; with an = int(1/en-1), and en = 1/en-1 - an. Then cn is the compound fraction built from the integers a0 through an.
To begin, a0 is the integer quotient p/q. (Remember, you want the greatest integer in p/q, even if p is negative.) Once a0 is set, e0 is the remainder (when p is divided by q), over q. At this point both numerator and denominator are positive.
To take the next step, take the reciprocal of the aforementioned fraction e0, let a1 be the quotient, and let e1 be the remainder, over the denominator. Continue this process and you are running the gcd algorithm. When en = 0, the process stops. You can consider the sequence of continued fractions as finite, or you can extend the sequence by repeating cn forever. It's a matter of taste. I will call the sequence finite.
But is cn really equal to r? It is if r is an integer. Proceed by induction on n.
The continued fraction that begins with a1, running through an, is truly equal to the rational number that created it, namely 1/e0. Its reciprocal is e0. Add a0 to this to get cn, which is equal to r. The map from rationals to finite sequences, and back to rationals, is faithful. The same value of r appears.
Note that a finite sequence so produced has each ai positive, except perhaps for a0. Also, the last an, beyond a0, cannot be 1. This would make 1/en-1 equal to 1, whence en-1 = 1, and we should have incremented an-1.
Now we're ready for the converse. Start with any finite sequence of integers a0 through an, such that a1 through an are positive, and an (for n > 0) is not 1. build the corresponding continued fraction cn and call it r. Does r lead to this particular sequence? It does if n = 0. For larger n, the sequence beginning with A1 builds a real number, greater than1, that I will call 1/e0, which in turn yields the sequence starting with a1. Now cn = a0+e0. Since e0 < 1, unraveling cn yields a0, with remainder e0, and the rest of the sequence, starting at a1 is produced from there. That completes the inductive step. Rational numbers and finite sequences of integers (constrained as above) correspond. Unlravel r to obtain the sequence a0 through an, and build cn to get back to r.
Clearly c0 = a0 = 3, the greatest integer in π.
We can add 1/7 to this and still be greater than π, while 3.125 is smaller, hence a1 = 7, and c1 is the familiar 22/7.
Now it's time to tweak 7 by a reciprocal. Add 1/15 to 7, and we are still smaller than π. This is the best we can do, hence a2 = 15, and c2 = 333/106.
If you take the next step, a3 = 1, and c3 = 355/113. You can continue this as long as you like.
0, 1, 1/2, 2/3, 3/5, 5/8, 8/13, 13/21, …
Look at the numerators and you may recognize the fibonacci sequence. The denominators run the same sequence shifted by 1. Therefore cn = fib(n)/fib(n+1).
As described on the aforementioned page, the fibonacci sequence is exponential. Specifically, fib(n) approaches φn/sqrt(5), where φ is the golden ratio, approximately 1.618034. The quotient φn/φn+1 approaches 1/φ. We have built a continued fraction that approaches a real number, namely 1/φ, which is the same as φ-1, approximately 0.618034.
Change a0 to 1 in the above, so that each ai = 1, and cn approaches φ-1+1, or φ. This is a continued fraction that approaches the golden ratio. We will use this result to prove convergence in general.
Consider the difference between cm and cn. When am is increased, 1/am is decreased. The two quantities are inversely related. Similarly, am-1+1/am changes inversely with the change in am. Take the reciprocal and find an expression that changes directly with am. Add am-2 and find an expression that changes directly with am. Take the reciprocal and find an expression that changes inversely with am. By induction, the difference between cm and cn is maximized when am is changed as much as possible. As shown above, the change is at most 1. Thus it is enough to ask how cm changes as am advances by 1.
The greatest change in 1/am, and in cm, occurs when am moves from 1 to 2. Thus it is enough to ask how cm changes as am advances from 1 to 2. In other words, let am = 1.
As am moves from 1 to 2, the next compound fraction moves from 1/(am-1+1) to 1/(am-1+½). The greater this change, the greater the change in cm. This is maximized when am-1 = 1.
Continue the above all the way back to a1. In each case the difference is maximized when ai = 1. Therefore the difference between cm and cn is bounded by the difference, as am moves from 1 to 2, of a canonical continued fraction whose integer elements are all equal to 1.
This continued fraction was described above. Set a0 = 0, for convenience, and cm = fib(m)/fib(m+1). Push am up to 2 and find fib(m+1)/fib(m+2). Remember that these quotients approach 1/φ for large m. Therefore, for any ε, there is some m, such that fib(m)/fib(m+1) and fib(m+1)/fib(m+2) are within ε of each other. This constrains the difference between cm and cn, for all n beyond m, and that is exactly the criteria we need to show the sequence of continued fractions is cauchy. It therefore converges to a real number r.
In summary, every sequence of continued fractions, built from a sequence of integers (positive beyond a0), approaches a real number. We have established a map from infinite sequences of integers into the reals. Conversely, each real number leads to a sequence of integers and a sequence of continued fractions, as described at the top of this page. Are these maps faithful inverses of each other? They are, and we'll prove it, but first we need to get a handle on the denominators of cn.
Remember that each ai is positive, except perhaps a0. Increase any ai (for i > 0), and the fraction produced by bringing in ai becomes larger. Specifically, the numerator is larger. When flipped, the denominator is larger, which makes the next numerator larger, and so on. All the numerators and denominators are larger from that point on, and cn has a larger denominator. Therefore the smallest possible denominator for cn occurs when each ai, from a1 to an, equals 1.
We have already discussed this continued fraction. The denominator of cn is fib(n+1), which is (for all practical purposes) φn+1/sqrt(5). I'll call this 0.72 times φn. This result will come in handy later on.
We will actually prove something stronger, the difference between cn and cn seeded by an+1 is bounded by 1/(t2+t). Since r always fits within these two continued fractions, and since 1/t2 > 1/(t2+t), this will suffice.
Note that a0 never really enters into the picture. We could subtract a0 from r, and from the continued fractions of r - and the difference between r and any cn, or the difference between cn and cnadjusted by an+1, does not change. Therefore it is sufficient to prove this theorem for r between 0 and 1. In other words, as a matter of convenience, a0 = 0.
Now start with c1. The two fractions that bracket r are 1/a1 and 1/(a1+1). The difference is 1 over a1×(a1+1), which is precisely the expression we are looking for.
The inductive assumption is that cn-1 is close to the same continued fraction when an-1 is incremented, according to the denominator of cn-1. This holds for every continued fraction out to length n-1. Fix an r between0 and 1 and spin off the continued fractions out to cn. Let the continued fraction from a1 out to an equal s/t. Therefore cn = t/s. Adjust an by 1 and adjust s/t by at most 1/(t2+t). Get a common denominator and write this as (st+s±1)/(t2+t). Take the reciprocal and subtract t/s, giving t/(s×(st+s±1)).
Since a1 is nonzero, the numerator is strictly larger than the denominator. In other words, s > t. Replace s±1 with t, which can only make the denominator smaller. The expression simplifies to 1/(s×(s+1)), and that completes the proof.
In summary, continued fractions that are "adjacent" are within 1/t2 of each other, and within 1/t2 of r. Since denominators increase quickly, the continued fractions of r approach r. For any real number, r spins off a sequence of continued fractions, that converges to r. The sequence is finite iff r is rational.
Is this a bijection? Can we go the other way? Consider an infinite sequence of continued fractions c0 c1 c2 c3 etc, defined by a0 a1 a2 a3 etc. Let it converge to a real number r, and suppose r creates another sequence of continued fractions d0 d1 d2 d3 etc, based on the integers b0 b1 b2 b3 etc, such that an ≠ bn, and n is minimal.
Since d is created from r, d converges to r. Thus c and d both converge to r. Assume r is irrational, hence d is also an infinite sequence.
Suppose n > 0, hence a0 = b0. Pull a0 down to 0. This subtracts a0 from r, leaving another irrational number. It also subtracts a0 from each ci and each di. Both series still converge to the new r. Take the reciprocal of r, and of each ci and di beyond i = 0. These are the continued fractions beginning with a1 and b1. Repeat the above process all the way down to n. In other words, the problem has been reduced to two sequences that converge to r, yet a0 ≠ b0.
Assume a0 < b0 and subtract a0 across the board. Now r is strictly between 0 and 1. We know the inequalities are strict, since r is irrational. Each di begins with b0 plus something positive. Since b0 is also positive, each di is at least 1, and d cannot converge to r. This is a contradiction, hence ci converges to r, which recreates ai and ci.
We still need to consider an infinite sequence of continued fractions that converges to a rational number. Start with r an integer. The reverse sequence has b0 = r, and stops there. Subtract b0 across the board, so that r = 0.
If a0 ≥ 1, each ci ≥ 1, and c cannot converge to 0.
The contribution of 1/(a1+1/(a2+1/(a3+…))) is bounded by 1. If a0 ≤ -2, each ci ≤ -1, and c cannot converge to 0. Thus a0 is 0 or -1.
Suppose a0 = 0. Beyond i = 1, a1 is tweaked by something between 0 and 1. Take the reciprocal and the result is bounded by 1/a1 and 1/(a1+1). Since each ci is bounded above 0, c cannot converge to 0.
Suppose a0 = -1. We just showed that ci is trapped between -1+1/a1 and -1+1/(a1+1). This forces a1 = 1. Yet a1 is adjusted by something between 1/a2 and 1/(a2+1). This bounds a1 above 1+ε, which keeps the reciprocal below 1-ε, which keeps ci below -ε. Since c cannot converge to 0, we have a contradiction. An infinite sequence of continued fractions cannot approach an integer.
Suppose an infinite sequence of continued fractions converges to a rational number r. Remember that r is not an integer, and is not 0. Spin off the finite sequence bi and di as before. If a0 = b0, subtract this value across the board, then take reciprocals. This resets the sequences at a1 and b1. They both converge to the new value of r, which remains rational. If r is an integer we have a contradiction. So we can keep going. Since b is a finite sequence the process must stop. At this point a0 ≠ b0.
Subtract b0 across the board, so that r is a rational number whose derived sequence starts with 0. Remember that the representation of a rational number is faithful. The first coefficient that r creates is 0, and r is strictly between 0 and 1. If a0 is negative then each ci is bounded by 0, and c cannot approach r. If a0 ≥ 1 then each ci ≥ 1, and c cannot approach r. By assumption a0 is not 0, since it would then equal b0. We have reached a contradiction. Every infinite sequence of continued fractions converges to an irrational number, And this correspondence, like the rationals, is one to one.
Recall that the continued fractions of p/q run the gcd algorithm. They also converge to r according to the square of the denominator. And the denominators increase as φn. Put this all together and the gcd algorithm terminates in n steps, where φ2n attains the precision of q. Evaluate φ2 and get 2.618. Take the log base 2 and get 1.3885. Thus the number of steps is actually the number of bits times 0.72. This is two decimal digits every five steps. And this does not include any improvements you might realize by taking q - the remainder, if that proves to be smaller.