File RandomNumbers.h

↰ Parent directory (ADS/numeric)

Random numbers as Knuth treats them (chapter 3), beyond the book:

Definition (ADS/numeric/RandomNumbers.h)

Detailed Description

  • LinearCongruential, :math:` X_{n+1} = ( a X_n + c ) bmod m ` (3.2.1), a UniformRandomBitGenerator; with the theorem of Hull and Dobell its period is m exactly when c and m are coprime, a - 1 is a multiple of every prime factor of m, and of 4 if m is; minstd() gives the multiplicative generator of Park and Miller, and mmix() that of Knuth for MMIX, :math:` m = 2^{64} `;

  • chiSquare() and kolmogorovSmirnov() are the two general tests of 3.3.1: the statistic :math:` V = sum ( Y_s - n p_s )^2 / ( n p_s ) ` of the counts in k categories, to compare with the :math:` chi^2 ` distribution with k - 1 degrees of freedom, and the statistics :math:` K^+_n , K^-_n ` of the largest deviations of the empirical distribution from the continuous one; serialTest() applies the first to the pairs of consecutive numbers (3.3.2B);

  • spectralTest2() is the spectral test in two dimensions (3.3.4): the points :math:` ( X_n , X_{n+1} ) ` of a linear congruential generator lie on parallel lines at the distance :math:` 1 / nu_2 , where :math: nu_2 ` is the length of the shortest nonzero vector :math:` ( u , v ) ` with :math:` u + a v equiv 0 pmod m , found by the reduction of Gauss and Lagrange of the basis :math: ( m , 0 ) , ( -a , 1 ) ; a good generator has :math: nu_2 ` near :math:` sqrt{m} `;

  • shuffle() is Algorithm 3.4.2P (Fisher and Yates, Durstenfeld), every permutation equally likely; selectionSampling() is Algorithm 3.4.2S, n of N records in order with one pass, and reservoirSampling() is Algorithm 3.4.2R, n records from a stream of unknown length.

The contracts [see File Contract.h]: m >= 1 and a , c < m for the generator, positive expected counts for the tests, n <= N for the samplings. The functions are defined in RandomNumbers.tpp.

    1. Knuth, The Art of Computer Programming, vol. 2, 3rd ed., Addison-Wesley, 1998, chapter 3

    1. Hull, A. R. Dobell, Random number generators, SIAM Review 4(3), 230-254, 1962, doi:10.1137/1004061

    1. Park, K. W. Miller, Random number generators: good ones are hard to find, Communications of the ACM 31(10), 1192-1201, 1988, doi:10.1145/63039.63042

    1. Fisher, F. Yates, Statistical Tables for Biological, Agricultural and Medical Research, Oliver and Boyd, 1938, and R. Durstenfeld, Algorithm 235: random permutation, Communications of the ACM 7(7), 420, 1964, doi:10.1145/364520.364540

    1. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software 11(1), 37-57, 1985, doi:10.1145/3147.3165

    1. Brent, An improved Monte Carlo factorization algorithm, BIT Numerical Mathematics 20(2), 176-184, 1980, doi:10.1007/BF01933190 (the detection of the cycle of period())

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Functions