364 ARITHMETIC (Best web hosting) 4.5.3 44. [A42.5] Suppose we are
364 ARITHMETIC 4.5.3 44. [A42.5] Suppose we are doing fixed slash arithmetic with mediant rounding, where the fraction (U/U ) is representable if and only if 1 1~1< M and 0 5 1~ < N and gcd(u, 2~ ) = 1. Prove or disprove the identity ((U/U ) @ (U/W )) 8 (V/W ) = (u/u ) for all representable (U/U ) and (U/W ), provided that U < v% and no overflow occurs. 45. [HM48] Develop the analysis of algorithms for computing the greatest common divisor of three or more integers. 4.5.4. Factoring into Primes Several of the computational methods we have encountered in this book rest on the fact that every positive integer n can be expressed in a unique way in the form n=w2...pt, Pl I P2 5 ... I Pt, (1) where each pk is prime. (When n = 1, this equation holds for t = 0.) It is unfortunately not a simple matter to find this prime factorization of n, or to determine whether or not n is prime. So far as anyone knows, it is a great deal harder to factor a large number n than to compute the greatest common divisor of two large numbers m and n; therefore we should avoid factoring large numbers whenever possible. But several ingenious ways to speed up the factoring process have been discovered, and we will now investigate some of them. Divide and factor. First let us consider the most obvious algorithm for factor- ization: If n > 1, we can divide n by successive primes p = 2, 3, 5, . . . until discovering the smallest p for which n mod p = 0. Then p is the smallest prime factor of n, and the same process may be applied to n c n/p in an attempt to divide this new value of n by p and by higher primes. If at any stage we find that nmodp # 0 but Ln/pJ 5 p, we can conclude that n is prime; for if n is not prime, then by (1) we must have n 2 pf, but pl > p implies that ~~2(~+1)~>~(~+1)>~~+(nmod~)~lnl~J~+(nmod~)=n. This leads us to the following procedure: Algorithm A (Factoring by division). Given a positive integer N, this algorithm finds the prime factors pl 5 p2 5 … 5 p, of N as in Eq. (1). The method makes use of an auxiliary sequence of trial divisors 2 = do < dl < dz < da < . , (2) which includes all prime numbers 5 m (and which may also include values that are not prime, if it is convenient to do so). The sequence of d s must also include at least one value such that dk 2 m. Al. [Initialize.] Set t t 0, k t 0, n t N. (During this algorithm the variables t, k, n are related by the following condition: % = N/p1 . . .pt, and n has no prime factors less than dk. ) A2. [n = l?] If n = 1, the algorithm terminates.