330 ARITHMETIC (Web host server) 4.5.2 L3. [Emulate Euclid.] Set T
330 ARITHMETIC 4.5.2 L3. [Emulate Euclid.] Set T t A -qC, A t C, C t T, T + B -qD, B c D, D c T, T c C -q6, ii c 6, 6 t T, and go back to step L2. (These single-precision calculations are the equivalent of multiple-precision operations, as in (28), under the conventions of (29).) L4. [Multiprecision step.] If B = 0, set t t umod v, u t v, v t t, using multiple-precision division. (This happens only if the single-precision opera- tions cannot simulate any of the multiple-precision ones. It implies that Euclid s algorithm requires a very large quotient, and this is an extremely rare occurrence.) Otherwise, set t c Au, t t t+Bv, w e Cu, w t w+Dv, u t t, 21 t w (using straightforward multiple-precision operations). Go back to step Ll. 1 The values of A, B, C, D remain as single-precision numbers throughout this calculation, because of (31). Algorithm L requires a somewhat more complicated program than Algo- rithm B, but with large numbers it will be faster on many computers. The binary technique of Algorithm B can, however, be speeded up in a similar way (see exercise 34), to the point where it continues to win. Algorithm L has the advantage that it can readily be extended, as in Algorithm X (see exercise 17); furthermore, it determines the sequence of quotients obtained in Euclid s algorithm, and this yields the regular continued fraction expansion of a real number (see exercise 4.5.3-18). Analysis of the binary algorithm. Let us conclude this section by studying the running time of Algorithm B, in order to justify the formulas stated earlier. An exact determination of the behavior of Algorithm B appears to be ex- ceedingly difficult to derive, but we can begin to study it by means of an ap- proximate model of its behavior. Suppose that u and v are odd numbers, with u > v and 1kuJ = m, [lgvl = 72. (32) (Thus, u is an (m + 1)-bit number, and v is an (n + 1)-bit number.) Algorithm B forms u -v and shifts this quantity right until obtaining an odd number u that replaces u. Under random conditions, we would expect to have u = (u -v)/2 about one-half of the time, u = (u -v)/4 about one-fourth of the time, u = (u -v)/8 about one-eighth of the time, and so on. We have ]lg ~ 1 = m -k -T, (33) where k is the number of places that u -v is shifted right, and where r is [lgu] -]lg(u -v)l, the number of bits lost at the left during the subtraction of v from u. Note that r 5 1 when m 2 n + 2, and r 2 1 when m = n. For simplicity, we will assume that r = 0 when m # n and that r = 1 when m = n, although this lower bound tends to make u seem larger than it usually is. The approximate model we shall use to study Algorithm B is based solely on the values m = Llgu] and n = [lgvJ throughout the course of the algorithm,