rand

Calc Software Package for Number Calc

NAME
    rand - subtractive 100 shuffle pseudo-random number generator

SYNOPSIS
    rand([[min, ] max])

TYPES
    min		integer
    max		integer

    return	integer

DESCRIPTION
    Generate a pseudo-random number using an subtractive 100 shuffle generator.
    We return a pseudo-random number over the half closed interval [min,max).
    By default, min is 0 and max is 2^64.

    The shuffle method is fast and serves as a fairly good standard
    pseudo-random generator.   If you need a fast generator and do not
    need a cryptographically strong one, this generator is likely to do
    the job.  Casual direct use of the shuffle generator may be
    acceptable.	 For a much higher quality cryptographically strong
    (but slower) generator use the Blum-Blum-Shub generator (see the
    random help page).

    Other arg forms:

	rand()		Same as rand(0, 2^64)
	rand(max)	Same as rand(0, max)

    The rand generator generates the highest order bit first.  Thus:

	rand(256)

    will produce the save value as:

	(rand(8) << 5) + rand(32)

    when seeded with the same seed.

    The rand generator has two distinct parts, the subtractive 100 method
    and the shuffle method.  The subtractive 100 method is described in:

	"The Art of Computer Programming - Seminumerical Algorithms",
	Vol 2, 3rd edition (1998), Section 3.6, page 186, formula (2).

    The "use only the first 100 our of every 1009" is described in
    Knuth's "The Art of Computer Programming - Seminumerical Algorithms",
    Vol 2, 3rd edition (1998), Section 3.6, page 188".

    The period and other properties of the subtractive 100 method
    make it very useful to 'seed' other generators.

    The shuffle method is feed values by the subtractive 100 method.
    The shuffle method is described in:

	"The Art of Computer Programming - Seminumerical Algorithms",
	Vol 2, 3rd edition (1998), Section 3.2.2, page 34, Algorithm B.

    The rand generator has a good period, and is fast.	It is reasonable as
    generators go, though there are better ones available.  The shuffle
    method has a very good period, and is fast.	 It is fairly good as
    generators go, particularly when it is feed reasonably random
    numbers.  Because of this, we use feed values from the subtractive 100
    method into the shuffle method.

    The rand generator uses two internal tables:

	additive table - 100 entries of 64 bits used by the subtractive
			 100 method

	shuffle table - 256 entries of 64 bits used by the shuffle method
			feed by the subtractive 100 method from the
			subtractive table

    The goals of this generator are:

	* all magic numbers are explained

	    I (Landon Curt Noll) distrust systems with constants (magic
	    numbers) and tables that have no justification (e.g.,
	    DES).  I believe that I have done my best to justify all of
	    the magic numbers used.

	* full documentation

	    You have this source file, plus background publications,
	    what more could you ask?

	* large selection of seeds

	     Seeds are not limited to a small number of bits.  A seed
	     may be of any size.

    Most of the magic constants used by this generator ultimately are
    based on the Rand book of random numbers.  The Rand book contains
    10^6 decimal digits, generated by a physical process.  This book,
    produced by the Rand corporation in the 1950's is considered
    a standard against which other generators may be measured.

    The Rand book of numbers was groups into groups of 20 digits.  The
    first 100 groups < 2^64 were used to initialize the default additive
    table.  The size of 20 digits was used because 2^64 is 20 digits
    long.  The restriction of < 2^64 was used to prevent modulus biasing.

    The shuffle table size is longer than the 100 entries recommended
    by Knuth.  We use a power of 2 shuffle table length so that the
    shuffle process can select a table entry from a new subtractive 100
    value by extracting its low order bits.  The value 256 is convenient
    in that it is the size of a byte which allows for easy extraction.

    We use the upper byte of the subtractive 100 value to select the
    shuffle table entry because it allows all of 64 bits to play a part
    in the entry selection.  If we were to select a lower 8 bits in the
    64 bit value, carries that propagate above our 8 bits would not
    impact the subtractive 100 generator output.

    It is 'nice' when a seed of "n" produces a 'significantly different'
    sequence than a seed of "n+1".  Generators, by convention, assign
    special significance to the seed of '0'.  It is an unfortunate that
    people often pick small seed values, particularly when large seed
    are of significance to the generators found in this file.  An internal
    process called randreseed64 will effectively eliminate the human
    perceptions that are noted above.

    It should be noted that the purpose of randreseed64 is to scramble a
    seed ONLY.	We do not care if these generators produce good random
    numbers.  We only want to help eliminate the human factors & perceptions
    noted above.

    The randreseed64 process scrambles all 64 bit chunks of a seed, by
    mapping [0,2^64) into [0,2^64).  This map is one-to-one and onto.
    Mapping is performed using a linear congruence generator of the form:

	X1 <-- (a*X0 + c) % m

    with the exception that:

	0 ==> 0			(so that srand(0) acts as default)

    while maintaining a 1-to-1 and onto map.

    The randreseed64 constants 'a' and 'c' based on the linear
    congruential generators found in:

	"The Art of Computer Programming - Seminumerical Algorithms"
	by Knuth, Vol 2, 2nd edition (1981), Section 3.6, pages 170-171.

    We will select the randreseed64 multiplier 'a' such that:

	a mod 8 == 5			(based on note iii)
	0.01*m < a < 0.99*m		(based on note iv)
	0.01*2^64 < a < 0.99*2^64
	a is prime			(help keep the generators independent)

    The choice of the randreseed64 adder 'c' is considered immaterial
    according (based in note v).  Knuth suggests 'c==1' or 'c==a'.  We
    elect to select 'c' using the same process as we used to select
    'a'.  The choice is 'immaterial' after all, and as long as:

	gcd(c, m) == 1		(based on note v)
	gcd(c, 2^64) == 1
	gcd(a, c) == 1		(adders & multipliers will be more independent)

    The values 'a' and 'c for randreseed64 are taken from the Rand book
    of numbers.	 Because m=2^64 is 20 decimal digits long, we will
    search the Rand book of numbers 20 at a time.  We will skip any of
    the 100 values that were used to initialize the subtractive 100
    generators.	 The values obtained from the Rand book are:

	a = 6316878969928993981
	c = 1363042948800878693

    As we stated before, we must map 0 ==> 0 so that srand(0) does the
    default thing.  The randreseed64 would normally map as follows:

	0 ==> 1363042948800878693	(0 ==> c)

    To overcome this, and preserve the 1-to-1 and onto map, we force:

	0 ==> 0
	10239951819489363767 ==> 1363042948800878693

    One might object to the complexity of the seed scramble/mapping via
    the randreseed64 process.  But Calling srand(0) with the randreseed64
    process would be the same as calling srand(10239951819489363767)
    without it.	 No extra security is gained or reduced by using the
    randreseed64 process.  The meaning of seeds are exchanged, but not
    lost or favored (used by more than one input seed).

    The randreseed64 process does not reduce the security of the rand
    generator.	Every seed is converted into a different unique seed.
    No seed is ignored or favored.

    The truly paranoid might suggest that my claims in the MAGIC NUMBERS
    section are a lie intended to entrap people.  Well they are not, but
    if you that paranoid why would you use a non-cryprographically strong
    pseudo-random number generator in the first place?  You would be
    better off using the random() builtin function.

    The two constants that were picked from the Rand Book of Random Numbers
    The random numbers from the Rand Book of Random Numbers can be
    verified by anyone who obtains the book.  As these numbers were
    created before I (Landon Curt Noll) was born (you can look up
    my birth record if you want), I claim to have no possible influence
    on their generation.

    There is a very slight chance that the electronic copy of the
    Rand Book of Random Numbers that I was given access to differs
    from the printed text.  I am willing to provide access to this
    electronic copy should anyone wants to compare it to the printed text.

    When using the s100 generator, one may select your own 100 subtractive
    values by calling:

         srand(mat100)

    and avoid using my magic numbers.  The randreseed64 process is NOT
    applied to the matrix values. Of course, you must pick good subtractive
    100 values yourself!

EXAMPLE
    ; print srand(0), rand(), rand(), rand()
    RAND state 2298441576805697181 3498508396312845423 5031615567549397476

    ; print rand(123), rand(123), rand(123), rand(123), rand(123), rand(123)
    106 59 99 99 25 88

    ; print rand(2,12), rand(2^50,3^50), rand(0,2), rand(-400000, 120000)
    2 658186291252503497642116 1 -324097

LIMITS
    min < max

LINK LIBRARY
    void zrand(long cnt, ZVALUE *res)
    void zrandrange(ZVALUE low, ZVALUE high, ZVALUE *res)
    long irand(long max)

SEE ALSO
    seed, srand, randbit, isrand, random, srandom, israndom

## Copyright (C) 1999  Landon Curt Noll
##
## Calc is open software; you can redistribute it and/or modify it under
## the terms of the version 2.1 of the GNU Lesser General Public License
## as published by the Free Software Foundation.
##
## Calc is distributed in the hope that it will be useful, but WITHOUT
## ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
## or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU Lesser General
## Public License for more details.
##
## A copy of version 2.1 of the GNU Lesser General Public License is
## distributed with calc under the filename COPYING-LGPL.  You should have
## received a copy with calc; if not, write to Free Software Foundation, Inc.
## 59 Temple Place, Suite 330, Boston, MA  02111-1307, USA.
##
## @(#) $Revision: 29.4 $
## @(#) $Id: rand,v 29.4 2006/05/07 07:25:46 chongo Exp $
## @(#) $Source: /usr/local/src/cmd/calc/help/RCS/rand,v $
##
## Under source code control:	1996/01/01 02:16:09
## File existed as early as:	1996
##
## chongo <was here> /\oo/\	http://www.isthe.com/chongo/
## Share and enjoy!  :-)	http://www.isthe.com/chongo/tech/comp/calc/