334 ARITHMETIC 4.5.2 Table 1 NUMBER OF SUBTRACTIONS
334 ARITHMETIC 4.5.2 Table 1 NUMBER OF SUBTRACTIONS IN ALGORITHM B n n 0 12 3 4 5 0 12 3 4 5 0 1.00 2.00 2.50 3.00 3.50 4.00 1.00 2.00 2.50 3.00 3.50 4.00 0 1 2.00 1.00 2.50 3.00 3.50 4.00 2.00 1.00 3.00 2.75 3.63 3.94 1 2 2.50 2.50 2.25 3.38 3.88 4.38 2.50 3.00 2.00 3.50 3.88 4.25 2 3 3.00 3.00 3.38 3.25 4.22 4.72 3.00 2.75 3.50 2.88 4.13 4.34 3 4 3.50 3.50 3.88 4.22 4.25 5.10 3.50 3.63 3.88 4.13 3.94 4.80 4 5 4.00 4.00 4.38 4.72 5.10 5.19 4.00 3.94 4.25 4.34 4.80 4.60 5 m Predicted by model Actual average values m execution of Algorithm B, with u and v both odd, the corresponding path in the lattice model must satisfy the relation number of shifts + number of diagonal points f 2Llg gcd(u, v)] = m + n, since we are assuming that T in (33) is always either 0 or 1. The average value of [lggcd(u, w)J predicted by the lattice-point model is approximately 2 (see exercise 20). Therefore we have, for the total number of shifts, D=m+n-(in+&++&,)–* (41) =m+jn–g-Zj3Smn, when m 2 n, plus terms that decrease rapidly to zero for large n. To summarize the most important facts we have derived from the lattice- point model, we have shown that if u and w are odd and if [lg u] = m, [lg v] = n, then the quantities C and D that are the critical factors in the running time of Program B will have average values given by C = $m + i$ + O(l), D = m -I- i$ -I- O(l), m >_ 72. (42) But the model that we have used to derive (42) is only a pessimistic approxima- tion to the true behavior; Table 1 compares the true average values of C, com- puted by actually running Algorithm B with all possible inputs, to the values predicted by the lattice-point model, for small m and n. The lattice model is completely accurate when m or n is zero, but it tends to be less accurate when (m - n( is small and min(m, n) is large. When m = n = 9, the lattice-point model gives C = 8.78, compared to the true value C = 7.58. Empirical tests of Algorithm B with several million random inputs and with various values of m, n in the range 29 5 m,n 5 37 indicate that the actual average behavior of the algorithm is given by CR5 irn + 0.203n+ 1.9 - 0.4(0.6)m-n, m 2 n. (43) DZ m + 0.41n -0.5 - 0.7(0.6)m-n,