4.5.2 THE GREATEST COMMON DIVISOR 329 so long (Net web server)
4.5.2 THE GREATEST COMMON DIVISOR 329 so long as (27) holds. We can therefore avoid the multiple-precision operations of the first five steps, and replace them all by a multiple-precision calculation of -4u0 + 11~ and 7~ -19vo. In this case we obtain u = 1268728, v = 279726; the calculation can now proceed in a similar manner with u = 1268, U = 280, U = 1269, II = 279, etc. If we had a larger accumulator, more steps could be done by single-precision calculations; our example showed that only five cycles of Euclid s algorithm were combined into one multiple step, but with (say) a word size of 10 digits we could do about twelve cycles at a time. (Results proved in Section 4.5.3 imply that the number of multiple-precision cycles that can be replaced at each iteration is essentially proportional to the number of digits used in the single-precision calculations.) Lehmer s method can be formulated as follows: Algorithm L (Euclid s algorithm for large numbers). Let u,v be nonnegative integers, with u 2 v, represented in multiple precision. This algorithm computes the greatest common divisor of u and v, making use of auxiliary single-precision pdigit variables ti, 6, A, B, C, D, T, g, and auxiliary multiple-precision variables t and w. Ll. [Initialize.] If v is small enough to be represented as a single-precision value, calculate gcd(zl, v) by Algorithm A and terminate the computation. Otherwise, let C be the p leading digits of U, and let 6 be the corresponding digits of v; in other words, if radix-b notation is being used, Q t [u/b ] and 6 +– [v/b ], where k is as small as possible consistent with the condition 6 < bp. Set A t 1, B +-0, C +-0, D e 1. (These variables represent the coefficients in (28), where u=AuO+BvO, v = Cue + Dv,,, (29) in the equivalent actions of Algorithm A on multiple-precision numbers. We also have u =C+B, v = 6 + D, u = 6 + A, v = 6 + c (30) in terms of the notation in the example worked above.) L2. [Test quotient.] Set q + Kc + A)l(fi + C)l. If q # NC + B)/(fj + D)J, go to step L4. (This step tests if q # q , in the notation of the above example. Note that single-precision overflow can occur in special circumstances during the computation in this step, but only when Q = bp -1 and A = 1 or when 6 = bP -1 and D = 1; the conditions O