612 Appendix B
(a) Show that if 0<x<m, botha(xmodq)andr[x/q]lie in the range 0,...,m− 1
([z]is the largest integer smaller than or equal toz).
(b) Using this, show thataxmodmcan be found as:axmodm={
a(xmodq)−r[x/q] if this is≥ 0
a(xmodq)−r[x/q]+m otherwise.
(c) Findqandrform= 231 −1 anda=16 807(= 75 ).References
[1] N. A. Frigerio and N. Clarck,Trans. Am. Nucl. Soc., 22 (1975), 283–4.
[2] N. A. Frigerio, N. Clarck, and S. Tyler,Toward Truly Random Random Numbers, Report,
ANL/ES-26 Part 4. Argonne National Laboratory, 1978.
[3] D. E. Knuth,Seminumerical Algorithms.The Art of Computer Programming, vol. 2. Reading,
MA, Addison-Wesley, 1981.
[4] S. W. Park and K. W. Miller, ‘Random number generators: good ones are hard to find,’Commun.
ACM, 31 (1988), 1192–201.
[5] L. Schrage, ‘A more portable random number generator,’ACM Trans. Math. Software, 5 (1979),
132–8.
[6] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery,Numerical Recipes, 2nd edn.
Cambridge, Cambridge University Press, 1992.
[7] P. l’Ecuyer, ‘Efficient and portable combined random number generators,’Commun. ACM, 31
(1988), 742–9 and 774.
[8] G. Marsaglia, ‘Random numbers fall mainly in the planes,’Proc. Nat. Acad. Sci., 61 (1968),
25–8.
[9] A. M. Ferrenberg, D. P. Landau, and Y. J. Wong, ‘Monte Carlo simulations: hidden errors from
“good” random number generators,’Phys. Rev. Lett., 69 (1992), 3382–4.
[10] R. C. Tausworthe, ‘Random numbers generated by linear recurrence modulo 2,’Math. Comp.,
19 (1965), 201–9.
[11] S. Kirkpatrick and E. P. Stoll, ‘A very fast shift-register sequence random number generator,’
J. Comp. Phys., 40 (1981), 517–26.