🚀 go-pugleaf

In article <5goas8$s17@opus.vcn.bc.ca> landmark@vcn.bc.ca (Scott Phung) writes:
 > dik@cwi.nl (Dik T. Winter) wrote:
 > DW>             However if you have successive approximants pn/qn and pm/qm
 > DW> (m = n + 1) you also have to look through (pn+k.pm)/(qn+k.qm).  With
 > DW> pn=3, qn=1, pm=22, qm=7 and k=8 this gives you 179/57, which is better
 > DW> than 22/7.  Increasing k will give you better approximations until
 > DW> you hit k=16, when 333/106 (the next approximant) is already very much
 > DW> better.
 > 
 > Thanks for the information.  I hadn't learned about this, and it
 > can be useful (like say, what is the best approx. to pi with a
 > denominator less than 100, or the like).
 > 
 > Do you know if there is a way to calculate the value or approximate
 > value of k such that with this value of k, it will produce a better
 > approx. than pn, but not than pm? (Ie-in this case, k = 8).

[It has been over 10 years ago that I looked at this stuff, so some
of the minor details may be incorrect.]

Lets look at pi and use some notation.  The continued fraction expansion of
pi is [3; 7, 15, 1, 292, 1, ...], which does not terminate.  The first 3
is set off as the initial integer part (and that is the only element that
can be 0).  Now 3/1 = [3], 22/7 = [3; 7] and 333/106 = [3; 7, 15]
(terminating because they are rationals).  If we let k increase to 15 we
get the next approximant, 333/106 (I made an error here in my original
post); and it is not by coincidence that the last number in the expansion
of 333/106 is also 15.  Better approximations start for k one half of that
number (I disremember whether it is also so for even numbers or that you
have to start one further).

 > Or does a such a calculation not exist?  I imagine in the gap
 > between 333/106 and 355/113, there does not exist any rational
 > number more accurate than 333/106 but less accurate than 355/113.

That is right if you modify your statement to "any rational number
with denominator between 106 and 113".  Because the first number omitted
from the continued fraction is 1, only k=1 would work but that gives you
the next approximant: (22+333)/(7+106) = 355/113.  So when the first
number omitted is 1, there is no intermediate to look at.  Subsequent
approximants alternate between being too small and too large.  Intermediates
are all on the same side as the next approximant.
 > 
 > Does this method also work for other irrational numbers like
 > square roots, nth roots, quadratic irrationals, e, etc?

Yes, even for rationals themselves.  For instance, the common rational
constant 2.54 has continued fraction expansion [2; 1, 1, 5, 1, 3].
Subsequent approximants from this are 2, 3, 5/2, 28/11, 33/13, 127/50.
And we can get some intermediate approximants.  A large number in the
approximation indicates that at that place the denominator will increase
by a large part.  Also the numbers in the continued fraction expansion
of algebraic numbers can not get "too large" because rationals can not
approximate them "too close".  (For some notion of "too large" and
"too close" which can be quantified.)

 > It's also quite hard to beleive (for me) how continued fractions
 > don't pick up these 'holes'.

The reason you can also look at the intermediate forms is because
the continued fraction approximants only approximate closest in some
sense (it has to do with the difference compared to 1/q, where q
is the denominator of the approximant).  When you also look at the
intermediates you get closest approximation in another sense.
Given two successive intermediates (including approximants) pn/qn
and pm/qm than there is *no* rational number other than pn/qn closer
to the number approximated with a denominator smaller than pm.  (A
bit garbled, I hope you get the meaning.)

On computers continued fraction approximations are very useful in
fixed point arithmetic.
-- 
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/