4.5.3 ANALYSIS OF EUCLID S ALGORITHM (Frontpage web hosting) 345 value of
4.5.3 ANALYSIS OF EUCLID S ALGORITHM 345 value of n mod k is less than the average value of i k, in the range 1 5 k 5 n: En— 1 1441 + 1 n c( 2 > 1141n = 1-g n+O(logn) (21) ( > (cf. exercise 4.5.2-10(c)). This is only about .1775n, not .25n; so the value of nmod k tends to be smaller than the above model predicts, and Euclid s algorithm works faster than we might expect. A continuous model. The behavior of Euclid s algorithm with v = N is essen- tially determined by the behavior of the regular continued fraction process when x = O/N, l/N, . . . , (N -1)/N. Assuming that N is very large, we are led naturally to a study of regular continued fractions when X is a random real number uniformly distributed in [ 0,l). Therefore let us define the distribution function F,(z) = probability that X, 5 5, for 0 5 5 5 1, (22) given a uniform distribution of X = X0. By the definition of regular continued fractions, we have Fe(z) = z, and F,+i(z) = c probability that (k 2 l/Xn 5 k + x) k>l = c probability that (l/(k + CT) 5 X, 5 l/k) k>l = c (%(1/k) -%(ll(k + 4)). (23) k>l If the distributions Fe(s), Fi(z), . . . defined by these formulas approach a limiting distribution F,(z) = F(z), we will have F(z) = c (W/k) -J (ll(k + 4)). k>l One function that satisfies this relation is F(z) = log,(l + z), for any base b > 1; see exercise 19. The further condition F(1) = 1 implies that we should take b = 2. Thus it is reasonable to make a guess that F(z) = lg(1 + z), and that F,(z) approaches this behavior.