Using D.E. Littlewood's Euclidean Algorithm Approach To Obtain The Best Rational Approximations

 Mathematics legend Dudley E. Littlewood developed an interesting approach to obtain the best rational approximation, say for the value of a fraction. As he puts it in his timeless monograph 'The Skeleton Key Of Mathematics' (p. 27, Euclid's Algorithm):

"Clearly the fraction 1/3 is simpler than the corresponding decimal, 0.33333.... therefore it is of interest to study the best rational approximations. There will be a series of best approximations according to the degree of accuracy required."

He then starts with the rational approximation p/q, with the intent of finding a simpler fraction - call it p'/ q' - which will give as close an approximation as possible to p/q.  In this respect, the denominator of the difference, i.e.

p/q - p'/q  can be no greater than the product q q'. So the difference can't be less than 1/ qq'.  In effect one is seeking a simpler fraction p'/q'  such that:

p/q - p'/q' =   +  1/qq'

This gives: q' p  - p'q =    + 1   

The numbers p', q' are just those that can be obtained in Euclid's algorithm, which we've encountered in previous posts, e.g.

Brane Space: The Euclidean Algorithm and the Path to Continued Fractions

Following the use of continued fractions in that post, consecutive quotients can be used in executing the algorithm to find the best approximation too p/q.

And so one may write, following Littlewood:

where:

is usually used for more concise notation,

In the words of Littlewood(ibid.)

"It can then be shown that the remainder of the fraction, when reduced to the form of an ordinary fraction, gives the first approximation p'/q' as obtained from Euclid's Algorithm.

In this sense, the fraction:

a₁   +  1/+ a₂  + a₃ +........+ a_r

is called the rth convergent of the continued fraction."

  The continued fractions and approximations for  p  hold particular interest for Littlewood. For example. Littlewood gives the first twelve terms for the continued fraction as:

Littlewood notes the continued fraction will converge more rapidly if:

 "in the consecutive divisions the nearest integer is taken instead of the greatest integer less than the remainder of the fraction. Some of the remainders thus become negative, but the denominator 1 never appears. This has the effect of cutting off the comparatively inaccurate convergents.  Following this practice the first 12 terms given above for   p may be compressed into 7 in the form":

                                                    

 Littlewood also developed an approach to congruences using the Euclidean Algorithm.  This will be examined in another future post.