Hosting web - 328 ARITHMETIC 4.5.2 we don t really mind having
328 ARITHMETIC 4.5.2 we don t really mind having a large quotient 4, since Euclid s algorithm makes a great deal of progress when it replaces u by u mod v in such a case. A significant improvement in the speed of Euclid s algorithm when high- precision numbers are involved can be achieved by using a method due to D. H. Lehmer [AMM45 (1938), 227-2331. Working only with the leading digits of large numbers, it is possible to do most of the calculations with single-precision arith- metic, and to make a substantial reduction in the number of multiple-precision operations involved. We save a lot of time by doing a virtual calculation instead of the actual one. For example, let us consider the pair of eight-digit numbers u = 27182818, v = 10000000, assuming that we are using a machine with only four-digit words. Let U = 2718, v = 1001, u = 2719, v = 1000; then u//v and u /v are approximations to u/v, with u /v < u/v < U /V . (27) The ratio U/V determines the sequence of quotients obtained in Euclid s algo- rithm. If we carry out Euclid s algorithm simultaneously on the single-precision values (u , v ) and (u , v ) until we get a different quotient, it is not difficult to see that the same sequence of quotients would have appeared to this point if we had worked with the multiple-precision numbers (u, v). Thus, consider what happens when Euclid s algorithm is applied to (u , v ) and to (u , v ): 21′ 21′ q’ U” 21″ q’ 2718 1001 2 2719 1000 2 1001 716 1 1000 719 1 716 285 2 719 281 2 285 146 1 281 157 1 146 139 1 157 124 1 139 7 19 124 33 3 The first five quotients are the same in both cases, so they must be the true ones. But on the sixth step we find that q’ # q”, so the single-precision calculations are suspended. We have gained the knowledge that the calculation would have proceeded as follows if we had been working with the original multiple-precision numbers: 21 V q uo vo 2 vo uo - 2vc 1 uo - 2vc -uo + 3vo 2 (28) -uo + 3vo 3uo - 8vo 1 3uo - 8vo -4uc + llvc 1 -4210 + llvc 7uc - 19vo ? (The next quotient lies somewhere between 3 and 19.) No matter how many digits are in u and V, the first five steps of Euclid s algorithm would be the same as (28)