356 ARITHMETIC 4.5.3 For example, M (0.843)(4.605 -0.347 (Hosting web)
356 ARITHMETIC 4.5.3 For example, M (0.843)(4.605 -0.347 -0.173 -0.322 -0.064) + 1.47 Fz 4.59; the exact value of TIOOis 4.56. We can also estimate the average number of division steps when u and v are both uniformly distributed between 1 and N, by calculating (55) Assuming formula (53), exercise 27 shows that this sum has the form 7 In N + O(l), and empirical calculations with the same numbers used to derive Eq. 4.5.2-45 show good agreement with the formula 12ln2 ~ In N + 0.06. (57) 79 Of course we have not yet proved anything about T, and r, in general; so far we have only been considering plausible reasons why the above formulas ought to hold. Fortunately it is now possible to supply rigorous proofs, based on a careful analysis by several mathematicians. The leading coefficient (12 In 2)/ 7r2 in the above formulas was established first, in independent studies by John D. Dixon and Hans A. Heilbronn. Dixon [J. Number Theory 2 (1970), 414-4221 developed the theory of the F,(z) dis- tributions to show that individual partial quotients are essentially independent of each other in an appropriate sense, and proved that for all positive E we have IT(m, n) - ((12 In 2)/.rr2) lnnl < (lnn)(1/2)f except for exp(-c(c)(log N)E/2)N2 values of m and n in the range 1 5 m < 12 5 N, where C(E) > 0. Heilbronn s approach was completely different, working entirely with integers instead of con- tinuous variables. His idea, which is presented in slightly modified form in exer- cises 33 and 34, is based on the fact that r, can be related to the number of ways to represent n in a certain manner. Furthermore, his paper [Number Theory and Analysis, ed. by Paul Tur6n (New York: Plenum, 1969), 87-961 shows that the distribution of individual partial quotients 1, 2, . . . that we have discussed above actually applies to the entire collection of partial quotients belonging to the frac- tions having a given denominator; this is a sharper form of Theorem E. A still sharper result was obtained several years later by J. W. Porter [Mathematika 22