616 ANSWERS (Best web design) TO EXERCISES 4.5.4 cases where A,
616 ANSWERS TO EXERCISES 4.5.4 cases where A, is respectively (1,2,3,4). Since V, lies between (@ + l)/(An f 1) and 2&?/A,, it is likely that V, 2 2@y with probability about lg(1 + y). This is not much different from a uniform distribution, so something besides the size of V, must account for the unreasonable effectiveness of Algorithm E. 37. Apply exercise 4.5.3-12 to the number fi + R, to see that the periodic part begins immediately, and run the period backwards to verify the palindromic property. [It follows that the second half of the period gives the same V s as the first, and Algorithm E could be shut down earlier by terminating it when U = U or V = V in step E5. However, the period is generally so long, we never even get close to halfway through it, so there is no point in making the algorithm more complicated.] 38. [hf. Proc. Letters 8 (1979), 28-31.1 Note that xmody = x -y [x/y] can be computed easily on such a machine, and we can get simple constants like 0 = x -Z, 1 = Lx/x], 2 = 1-t 1; we can test x > 0 by testing whether x = 1 or Lx/(x -l)] # 0. (a) First compute 1 = [lgn] in O(logn) steps, by repeatedly dividing by 2; at the same time compute k = 2 and A + 22L+1 m O(logn) steps by repeatedly setting k + 2k, A t A2. For the main computation, suppose we know that t = A , u = (A + l)m, and v = m!; then we can increase the value of m by 1 by setting m t m + 1, t t At, u t (A + l)u, v + urn; and we can double the value of m by setting m c 2m, u c u2, v c ([u/t] modA)v2, t c t2, provided that A is sufficiently large. (Consider th e number u in radix-A notation; A must be greater than ( ;n ).) Now if n = (al . ac)z, let nJ = (al . a3)2; if m = nj and k = 2j and j > 0 we can decrease j by 1 by setting k c [k/2], m c 2m+ ([n/kJ mod 2). Hence we can compute nj! for j = 1, l- 1, . . , 0 in O(logn) steps. [Another solution, due to Julia Robinson, is to compute n! = LB /(f)] when B > (2n) + ; cf. AMM 80 (1973), 250-251, 266.1 (b) First compute A = 221+2 as in (a), then find the least k 2 0 such that 2k+ !modn = 0. If gcd(n, zk!) # 1, let f(n) be this value; note that this gcd can be computed in O(logn) steps by Euclid s algorithm. Otherwise we will find the least integer m such that (lmy2,) modn = 0, and let f(n) = gcd(m, n). (Note that in this case 2k < m 5 2 k-t1, hence [m/2] 5 2k and [m/2]! is relatively prime to n; therefore ( ,my2J) mod n = 0 iff m! mod n = 0. Furthermore n # 4.) To compute m with a bounded number of registers, we can use Fibonacci numbers (cf. Algorithm 6.2.1F). Suppose we know that s = F3, s = Fj+l, t = AF3, t = AF,+ , u = (A + 1)2F3, U = (A + 1)2F3+ , v = A , w = (A + 1)2m, (2z) mod n # 0, and ( ~$ ) = 0. It is easy to reach this state of affairs with m = F3+l, for suitably large j, in O(logn) steps; furthermore A will be larger than 22(m+S). If s = 1, we set f(n) = gcd(2m + 1, n) or gcd(2m + 2, n), whichever is # 1, and terminate the algorithm. Otherwise we reduce j by 1 as follows: Set r + s, s + s -s, s + r, r + t, t + lt /tJ, t + r, r + U, 1~ + ~u / LL], U + r; then if (lwu/vt] mod A) mod n # 0, set m + m + s, w + wu, v + vt. [Can this problem be solved with fewer than O(log n) operations? Can the smallest, or the largest, prime factor of n be computed in O(logn) operations?] SECTION 4.6 1. 9×2 + 7x + 9; 5×3 + 7×2 + 2x + 6.