Chapter 3 Random Numbers 1 3.1. Introduction 1 3.2. Generating Uniform Random Numbers 10 3.2.1. The Linear Congruential Method10 3.2.1.1. Choice of modulus12 3.2.1.2. Choice of multiplier 16 3.2.1.3. Potency 23 3.2.2. Other Methods 26 3.3. Statistical Tests 41 3.3.1. General Test Procedures for Studying Random Data 42 3.3.2. Empirical Tests 61 *3.3.3. Theoretical Tests80 3.3.4. The Spectral Test 93 3.4. Other Types of Random Quantities 119 3.4.1. Numerical Distributions119 3.4.2. Random Sampling and Shuffling 142 *3.5. What Is a Random Sequence? 149 3.6. Summary 184 Chapter 4 Arithmetic 194 4.1. Positional Number Systems 195 4.2. Floating Point Arithmetic 214 4.2.1. Single-Precision Calculations 214 4.2.2. Accuracy of Floating Point Arithmetic 229 *4.2.3. Double-Precision Calculations 246 4.2.4. Distribution of Floating Point Numbers 253 4.3. Multiple Precision Arithmetic 265 4.3.1. The Classical Algorithms265 *4.3.2. Modular Arithmetic 284 *4.3.3. How Fast Can We Multiply? 294 4.4. Radix Conversion 319 4.5. Rational Arithmetic 330 4.5.1. Fractions 330 4.5.2. The Greatest Common Divisor 333 *4.5.3. Analysis of Euclid's Algorithm 356 4.5.4. Factoring into Primes 379 4.6. Polynomial Arithmetic 418 4.6.1. Division of Polynomials 420 *4.6.2. Factorization of Polynomials 439 4.6.3. Evaluation of Powers 461 4.6.4. Evaluation of Polynomials 485 *4.7. Manipulation of Power Series 525 Answers to Exercises 538 Appendix A--Tables of Numerical Quantities 726 1. Fundamental Constants (decimal) 726 2. Fundamental Constants (octal)727 3. Harmonic Numbers, Bernoulli Numbers, Fibonacci Numbers 728 Appendix B--Index to Notations 730 Index and Glossary 735