J2ee Web Hosting, Perl Scripting And Developing Blog

86 RANDOM NUMBERS 3.3.3 not on c) have small partial quotients. In particular, the result of exercise 19 implies that the serial test on pairs will be satisfactorily passed if and only if a/m has no large partial quotients. The book Dedekind Sums by Hans Rademacher and Emil Grosswald (Math. Assoc. of America, Carus Monograph No. 16, 1972) discusses the history and properties of Dedekind sums and their generalizations. Further theoretical tests, including the serial test in higher dimensions, are discussed in Section 3.3.4. EXERCISES-First Set 1. [A4101 Express Z mod y in terms of the sawtooth and 6 functions. 2. [M20] Prove the replicative law, Eq. (10). 3. [HM%%?] What is the Fourier series expansion (in terms of sines and cosines) of the function f(s) = ((x))? b 4. [Ml91 If m = lOlo, what is the highest possible value of d (in the notation of Theorem P), given that the potency of the generator is lo? 5. [A4211 Carry out the derivation of Eq. (17). 6. [A4271 Let hh + kk = 1. (a) Show, without using Lemma B, that a@, k, c) = a(h, k, 0) + 12 for all integers c 2 0. (b) Show that if 0 < j < k, (c) Under the assumptions of Lemma B, prove Eq. (21). b 7. [A424] Give a proof of the reciprocity law (19), when c = 0, by using the general reciprocity law of exercise 1.2.4-45. b 8. [M.!?4] (L. Carlitz.) Let By generalizing the method of proof used in Lemma B, prove the following beautiful identity due to H. Rademacher: If each of p, Q, r is relatively prime to the other two, (The reciprocity law for Dedekind sums, with c = 0, is the special case r = 1.) 9. [A4401 Is there a simple proof of Rademacher s identity (exercise along the lines of the proof in exercise 7 of a special case?

3.3.3 THEORETICAL TESTS 85 correlation when a is a good multiplier; the choice c/m = 3 f $,a reduces C substantially only in cases like Example 2 above. And we are fooling ourselves in such cases, since the bad multiplier will reveal its deficiencies in other ways. Clearly we need a better estimate than (39); and such an estimate is now available thanks to Theorem D, which stems principally from the work of U. Dieter [Math. Comp. 25 (1971), 855-8831. Theorem D implies that o(a,m,c) will be small if the partial quotients of a/m are small. Indeed, by analyzing generalized Dedekind sums still more closely, it is possible to obtain quite a sharp estimate: Theorem K. Under the assumptions of Theorem D, we always have 1 aj-c uj+; 5 cr(h,k,c) 2 c uj+; c uj-;. (40) –2 c l 0, approaches large Cl

84 RANDOM NUMBERS 3.3.3 This is a very respectable value of C indeed. But the generator has a potency of only 3, so it is not really a very good source of random numbers in spite of the fact that it has low serial correlation. It is necessary to have a low serial correlation, but not sufficient. Example 3. Estimate the serial correlation for general a, m, and c. Solution. If we consider just one application of (30), we have da, m, c> 25:+6&-6:–o(m,u,c). Now la(m, a, c)l < a by exercise 12, and therefore 4a, m, 4 =:I 1-6C+6 : 2 (39) cz m U ( m ( m )> * The error in this approximation is less than (a + 6)/m in absolute value. The estimate in (39) was the first theoretical result known about the ran- domness of congruential generators. R. R. Coveyou [JACK 7 (1960), 72-741 obtained it by averaging over all real numbers x between 0 and m instead of con- sidering only the integer values (cf. exercise 21); then Martin Greenberger [Math. Comp. 15 (1961), 383-3891 gave a rigorous derivation including an estimate of the error term. So began one of the saddest chapters in the history of computer science! Although the above approximation is quite correct, it has been grievously misap- plied in practice; people abandoned the perfectly good generators they had been using and replaced them by terrible generators that looked good from the standpoint of (39). For more than a decade, the most common random number generators in daily use were seriously deficient, solely because of a theoretical advance. A little knowledge is a dangerous thing. If we are to learn by past mistakes, we had better look carefully at how (39) has been misused. In the first place people assumed uncritically that a small serial correlation over the whole period would be a pretty good guarantee of randomness; but in fact it doesn t even ensure a small serial correlation for 1000 consecutive elements of the sequence (see exercise 14). Secondly, (39) and its error term will ensure a relatively small value of C only when a z fi; therefore people suggested choosing multipliers near Jm. In fact, we shall see that nearly all multipliers give a value of C that is substantially less than l/fi, hence (39) is not a very good approximation to the true behavior. Minimizing a crude upper bound for C does not minimize C. In the third place, people observed that (39) yields its best estimate when c/m M 4 f ifi, since these values are the roots of 1 -6x + 6s2 = 0. In the absence of any other criterion for choosing c, we might as well use this one. The latter statement is not incorrect, but it is misleading at best, since experience has shown that the value of c has hardly any influence on the true value of the serial

3.3.3 THEORETICAL TESTS 83 Theorem D. Let h, k, c be integers with 0 < h 5 k, 0 2 c < k, and h relatively prime to k. Form the Euclidean tableau as defined in (33) above, and assume that the process stops after t steps with mt+l = 1. Let s be the smallest subscript such that c, = 0, and let h be defined by (36). Then a(h, k, c) = T + c (-l) + (a, -6b, + 6mjzJ+I) 1

82 RANDOM NUMBERS 3.3.3 Here ai = lmjlm,+~l, bj = lcjlmi+d (33) m,+2 = rnj modmj+r, ci+l = cy modmj+l, and it follows that 0 I m3+l < mj, 0 2 Cj < mj. (34) We have assumed for convenience that Euclid s algorithm terminates in (32) after four iterations; this assumption will reveal the pattern that holds in the general case. Since h and k were relatively prime to start with, we must have m5 = 1 and cg = 0 in (32). Let us further assume that cs # 0 but c4 = 0, in order to get a feeling for the effect this has on the recurrence. Equations (30) and (31) yield c(h, k, c) = o(m2, ml, cl) = f(m2, ml, cl) -4m3, m2, c2) = . . = f(m2, ml, cd -f(m3, m2, c2) + f(m4, m3, c3) -f(m5, m4, c4). The first part h/k + k/h of the formula for f(h, k, c) in (19) contributes ?$+Tp?$-$+~+~-~-~ to the total, and this simplifies to !!+(al+~)-~-(a~+~)+~+(a3+~)-~-a4 = h/k + al -a2 + a3 -a4. _ The next part l/hk of (19) also leads to a simple contribution; according to Eq. 4.5.3-9 and other formulas in Section 4.5.3, we have l/mlmz -l/m2m3 + l/m3m4 -l/m4m5 = h /k -1, (35) where h is the unique integer satisfying h h c 1 (modulo k), 0 < h < k. (36) Adding up all the contributions, and remembering our assumption that c4 = 0 (so that e(m4,cs) = 0, cf. (20)), we find that o(h, k, c) = y + (al -a2 + a3 -4 -6(bl -b2 + b3 - b4) 4 4 -++– m2m3 m3m4 in terms of the assumed tableau (32). Similar results hold in general:

3.3.3 THEORETICAL TESTS 81 which follows from the usual method of expanding the right-hand side into partial fractions. Moreover, if o(z) = (X -yl)(z -yz). . . (CC -y,), we have d(Yj) = (Yj -Yl). . . (Y.j -Yj-l)(Yj -Yj+1). . . (Yj -Ym); (28) this identity may often be used to simplify expressions like those in the left-hand side of (27). When h and Ic are relatively prime, the numbers w, w2, . . . , tik–l, ghP1 are all distinct; we can therefore consider formula (27) in the &&a; c ase of the polynomial (z -w). . . (zr - w~- )(x -5). . . (z -ch-l) = (x -l)(zh -1)/(x -1)2, obt aining the following identity in x: This identity has many interesting consequences, and it leads to numerous reci: procity formulas for sums of the type given in Eq. (26). For example, if we differentiate (29) twice with respect to x and let x + 1, we find that Replace j by h -j and by Ic - j in these sums and use (26) to get ~(kh,O)+ 3(h h -1) which is equivalent to the desired result. I Lemma B gives us an explicit function f(h, k, c) such that 4h, k, c) = f(h k c) -o(k h, c) (30) whenever 0 < h 5 k, 0 2 c < k, and h is relatively prime to k. From the definition (16) it is clear that a(k, h, c) = c(k mod h, h, c mod h). (31) Therefore we can use (30) iteratively to evaluate o(h, Ic, c), using a process that reduces the parameters as in Euclid s algorithm. Further simplifications occur when we examine this iterative procedure more closely. Let us set ml = k, m2 = h, cl = c, and form the following tableau: ml = alm2 + m3 cl =hmz+cz m2 = a2m3 + m4 Q = bzm3 + ~3 (32) m3 = a3m4 + m5 ~3 = km4 + ~4 m4 = a4m5 ~4 = km5 + ~5

80 RANDOM NUMBERS 3.3.3 If w is the complex kth root of unity elnilk, we have by Eq. 1.2.9-13 1 w-j?g(wjx) = ?-x7, if0 < r < k. i c Ojj ..,(X~-Xj-~)(XIXj)(Xj-Xj+l)~~~(xj-xn) = (x-x&r.(x-xn) ) (27)

3.3.3 THEORETICAL TESTS 79 Using the well-known formulas x= m(m-1) and 22 = m(m -1Pm -1) c 2 c 6 OOandcmodh=O. (20) Proof. We leave it to the reader to prove that, under these hypotheses, dh,k,c)+dk,h,c)=o(h,k,O)+rr(k,h,O)+~-6 i -3e(h,c)+3. (21) 11 (See exercise 6.) The lemma now must be proved only in the case c = 0. The proof we will give, based on complex roots of unity, is essentially due to L. Carlitz. There is actually a simpler proof that uses only elementary manipulations of sums (see exercise 7)-but the following method reveals more of the mathematical tools that are available for problems of this kind and it is therefore much more instructive. Let f(x) and g(s) be polynomials defined as follows: f(x) = 1+ Z +. . . + xk–l = (xk -1)/(X -1) g(x) = x + 2×2 + . . . + (k -l)xk- = zf (x) (22) = kxk/(x -1) - x(2 -1)/(x -l)!

78 RANDOM NUMBERS 3.3.3 since both z and s(z) take on each value of (0, 1, . . . , m - l} exactly once; hence (11) yields c [x– x~l=o<~m((~))+~. (12) O

3.3.3 THEORETICAL TESTS 77 Fig. 7. The sawtooth function ((z)), The proof of Theorem P indicates that a priori tests can indeed be carried out, provided that we are able to deal satisfactorily with sums involving the 1 J and [ 1 functions. In many cases the most powerful technique for dealing with floor and ceiling functions is to replace them by two somewhat more symmetrical ones: if z is an integer; 6(z) = [ZJ + 1 - 121 = 1 f if z is not an integer; (6) ((z)) = 2 - [ZJ - 4 + &Y(z) = z - [zl + 3 - g?(z). (7) The latter function is a sawtooth function familiar in the study of Fourier series; its graph is shown in Fig. 7. The reason for choosing to work with ((z)) rather than [z] or [zl is that ((z)) p assesses several very useful properties: K-z)) = -((z)); (8) ((2 + n)) = ((z)), integer n; (9) Nnz)) = C(z))+ ((z + k)) + . . . + ((2 + G)), integer n 2 1. 00) (See exercise 2.) In order to get some practice working with these functions, let us prove Theorem P again, this time without relying on exercise 1.2.4-37. With the help of Eqs. (7), (8), (9), we can show that I2- s(x) 1 x- s(x) = -(( —(x )) + f -+(x-;(x)) m m = x - s(x) -x-c;f >>+; m cc = x -4×1 +((qq)+; (11) m since (2 - s(z))/ m is never an integer. Now x - 4×1 = 0 c m O