help/rand

   1 NAME
   2     rand - subtractive 100 shuffle pseudo-random number generator
   3
   4 SYNOPSIS
   5     rand([[min, ] max])
   6
   7 TYPES
   8     min         integer
   9     max         integer
  10
  11     return      integer
  12
  13 DESCRIPTION
  14     Generate a pseudo-random number using an subtractive 100 shuffle generator.
  15     We return a pseudo-random number over the half closed interval [min,max).
  16     By default, min is 0 and max is 2^64.
  17
  18     The shuffle method is fast and serves as a fairly good standard
  19     pseudo-random generator.   If you need a fast generator and do not
  20     need a cryptographically strong one, this generator is likely to do
  21     the job.  Casual direct use of the shuffle generator may be
  22     acceptable.  For a much higher quality cryptographically strong
  23     (but slower) generator use the Blum-Blum-Shub generator (see the
  24     random help page).
  25
  26     Other arg forms:
  27
  28         rand()          Same as rand(0, 2^64)
  29         rand(max)       Same as rand(0, max)
  30
  31     The rand generator generates the highest order bit first.  Thus:
  32
  33         rand(256)
  34
  35     will produce the save value as:
  36
  37         (rand(8) << 5) + rand(32)
  38
  39     when seeded with the same seed.
  40
  41     The rand generator has two distinct parts, the subtractive 100 method
  42     and the shuffle method.  The subtractive 100 method is described in:
  43
  44         "The Art of Computer Programming - Seminumerical Algorithms",
  45         Vol 2, 3rd edition (1998), Section 3.6, page 186, formula (2).
  46
  47     The "use only the first 100 our of every 1009" is described in
  48     Knuth's "The Art of Computer Programming - Seminumerical Algorithms",
  49     Vol 2, 3rd edition (1998), Section 3.6, page 188".
  50
  51     The period and other properties of the subtractive 100 method
  52     make it very useful to 'seed' other generators.
  53
  54     The shuffle method is feed values by the subtractive 100 method.
  55     The shuffle method is described in:
  56
  57         "The Art of Computer Programming - Seminumerical Algorithms",
  58         Vol 2, 3rd edition (1998), Section 3.2.2, page 34, Algorithm B.
  59
  60     The rand generator has a good period, and is fast.  It is reasonable as
  61     generators go, though there are better ones available.  The shuffle
  62     method has a very good period, and is fast.  It is fairly good as
  63     generators go, particularly when it is feed reasonably random
  64     numbers.  Because of this, we use feed values from the subtractive 100
  65     method into the shuffle method.
  66
  67     The rand generator uses two internal tables:
  68
  69         additive table - 100 entries of 64 bits used by the subtractive
  70                          100 method
  71
  72         shuffle table - 256 entries of 64 bits used by the shuffle method
  73                         feed by the subtractive 100 method from the
  74                         subtractive table
  75
  76     The goals of this generator are:
  77
  78         * all magic numbers are explained
  79
  80             I (Landon Curt Noll) distrust systems with constants (magic
  81             numbers) and tables that have no justification (e.g.,
  82             DES).  I believe that I have done my best to justify all of
  83             the magic numbers used.
  84
  85         * full documentation
  86
  87             You have this source file, plus background publications,
  88             what more could you ask?
  89
  90         * large selection of seeds
  91
  92              Seeds are not limited to a small number of bits.  A seed
  93              may be of any size.
  94
  95     Most of the magic constants used by this generator ultimately are
  96     based on the Rand book of random numbers.  The Rand book contains
  97     10^6 decimal digits, generated by a physical process.  This book,
  98     produced by the Rand corporation in the 1950's is considered
  99     a standard against which other generators may be measured.
 100
 101     The Rand book of numbers was groups into groups of 20 digits.  The
 102     first 100 groups < 2^64 were used to initialize the default additive
 103     table.  The size of 20 digits was used because 2^64 is 20 digits
 104     long.  The restriction of < 2^64 was used to prevent modulus biasing.
 105
 106     The shuffle table size is longer than the 100 entries recommended
 107     by Knuth.  We use a power of 2 shuffle table length so that the
 108     shuffle process can select a table entry from a new subtractive 100
 109     value by extracting its low order bits.  The value 256 is convenient
 110     in that it is the size of a byte which allows for easy extraction.
 111
 112     We use the upper byte of the subtractive 100 value to select the
 113     shuffle table entry because it allows all of 64 bits to play a part
 114     in the entry selection.  If we were to select a lower 8 bits in the
 115     64 bit value, carries that propagate above our 8 bits would not
 116     impact the subtractive 100 generator output.
 117
 118     It is 'nice' when a seed of "n" produces a 'significantly different'
 119     sequence than a seed of "n+1".  Generators, by convention, assign
 120     special significance to the seed of '0'.  It is an unfortunate that
 121     people often pick small seed values, particularly when large seed
 122     are of significance to the generators found in this file.  An internal
 123     process called randreseed64 will effectively eliminate the human
 124     perceptions that are noted above.
 125
 126     It should be noted that the purpose of randreseed64 is to scramble a
 127     seed ONLY.  We do not care if these generators produce good random
 128     numbers.  We only want to help eliminate the human factors & perceptions
 129     noted above.
 130
 131     The randreseed64 process scrambles all 64 bit chunks of a seed, by
 132     mapping [0,2^64) into [0,2^64).  This map is one-to-one and onto.
 133     Mapping is performed using a linear congruence generator of the form:
 134
 135         X1 <-- (a*X0 + c) % m
 136
 137     with the exception that:
 138
 139         0 ==> 0                 (so that srand(0) acts as default)
 140
 141     while maintaining a 1-to-1 and onto map.
 142
 143     The randreseed64 constants 'a' and 'c' based on the linear
 144     congruential generators found in:
 145
 146         "The Art of Computer Programming - Seminumerical Algorithms"
 147         by Knuth, Vol 2, 2nd edition (1981), Section 3.6, pages 170-171.
 148
 149     We will select the randreseed64 multiplier 'a' such that:
 150
 151         a mod 8 == 5                    (based on note iii)
 152         0.01*m < a < 0.99*m             (based on note iv)
 153         0.01*2^64 < a < 0.99*2^64
 154         a is prime                      (help keep the generators independent)
 155
 156     The choice of the randreseed64 adder 'c' is considered immaterial
 157     according (based in note v).  Knuth suggests 'c==1' or 'c==a'.  We
 158     elect to select 'c' using the same process as we used to select
 159     'a'.  The choice is 'immaterial' after all, and as long as:
 160
 161         gcd(c, m) == 1          (based on note v)
 162         gcd(c, 2^64) == 1
 163         gcd(a, c) == 1          (adders & multipliers will be more independent)
 164
 165     The values 'a' and 'c for randreseed64 are taken from the Rand book
 166     of numbers.  Because m=2^64 is 20 decimal digits long, we will
 167     search the Rand book of numbers 20 at a time.  We will skip any of
 168     the 100 values that were used to initialize the subtractive 100
 169     generators.  The values obtained from the Rand book are:
 170
 171         a = 6316878969928993981
 172         c = 1363042948800878693
 173
 174     As we stated before, we must map 0 ==> 0 so that srand(0) does the
 175     default thing.  The randreseed64 would normally map as follows:
 176
 177         0 ==> 1363042948800878693       (0 ==> c)
 178
 179     To overcome this, and preserve the 1-to-1 and onto map, we force:
 180
 181         0 ==> 0
 182         10239951819489363767 ==> 1363042948800878693
 183
 184     One might object to the complexity of the seed scramble/mapping via
 185     the randreseed64 process.  But Calling srand(0) with the randreseed64
 186     process would be the same as calling srand(10239951819489363767)
 187     without it.  No extra security is gained or reduced by using the
 188     randreseed64 process.  The meaning of seeds are exchanged, but not
 189     lost or favored (used by more than one input seed).
 190
 191     The randreseed64 process does not reduce the security of the rand
 192     generator.  Every seed is converted into a different unique seed.
 193     No seed is ignored or favored.
 194
 195     The truly paranoid might suggest that my claims in the MAGIC NUMBERS
 196     section are a lie intended to entrap people.  Well they are not, but
 197     if you that paranoid why would you use a non-cryprographically strong
 198     pseudo-random number generator in the first place?  You would be
 199     better off using the random() builtin function.
 200
 201     The two constants that were picked from the Rand Book of Random Numbers
 202     The random numbers from the Rand Book of Random Numbers can be
 203     verified by anyone who obtains the book.  As these numbers were
 204     created before I (Landon Curt Noll) was born (you can look up
 205     my birth record if you want), I claim to have no possible influence
 206     on their generation.
 207
 208     There is a very slight chance that the electronic copy of the
 209     Rand Book of Random Numbers that I was given access to differs
 210     from the printed text.  I am willing to provide access to this
 211     electronic copy should anyone wants to compare it to the printed text.
 212
 213     When using the s100 generator, one may select your own 100 subtractive
 214     values by calling:
 215
 216          srand(mat100)
 217
 218     and avoid using my magic numbers.  The randreseed64 process is NOT
 219     applied to the matrix values. Of course, you must pick good subtractive
 220     100 values yourself!
 221
 222 EXAMPLE
 223     > print srand(0), rand(), rand(), rand()
 224     RAND state 2298441576805697181 3498508396312845423 5031615567549397476
 225
 226     > print rand(123), rand(123), rand(123), rand(123), rand(123), rand(123)
 227     106 59 99 99 25 88
 228
 229     > print rand(2,12), rand(2^50,3^50), rand(0,2), rand(-400000, 120000)
 230     2 658186291252503497642116 1 -324097
 231
 232 LIMITS
 233     min < max
 234
 235 LINK LIBRARY
 236     void zrand(long cnt, ZVALUE *res)
 237     void zrandrange(ZVALUE low, ZVALUE high, ZVALUE *res)
 238     long irand(long max)
 239
 240 SEE ALSO
 241     seed, srand, randbit, isrand, random, srandom, israndom
 242