c_cpp/etc/calc/help/rand

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