Conference rusure::math

724.0. "random number generation" by SQM::RICO () Tue Jun 30 1987 18:31

    The following discussion in the Run-Time Library notes file
    led me here.  Anybody have any comments on pseudo-random number
    generation, particularly the way MTH$RANDOM does it?

            Rico


                <<< CLT::SCAN$$DISK:[NOTES$LIBRARY]RTL.NOTE;1 >>>
                           -< VMS Run-Time Library >-
================================================================================
Note 271.0                         MTH$RANDOM                          3 replies
SQM::RICO                                            31 lines  30-JUN-1987 09:25
--------------------------------------------------------------------------------

    Pardon if this has already been discussed... I didn't notice
    anything doing a quick directory.  My questions concern MTH$RANDOM.

    MTH$RANDOM seems to have some deficiencies generating a set of
    truly random-looking numbers.  I realize that "random" numbers are
    really "pseudo-random" numbers arrived at by applying some
    algorithm to the seed value to generate a random value and a new
    seed.  Does anyone care to expound on this?

    I have noticed that a "low" seed value will always generate a "low"
    initial random number.  Specifically, when I used seeds in the range
    0 to 10000, the first random number generated was always between
    0 and .15.  Subsequent random numbers seem to begin covering the
    full range of 0 to 1.

    The doc says that the method for updating the seed is:

        SEED = (69069*SEED+1) MOD 2^32

    What is the theory behind this?  It also says that the high 24
    bits of the seed are converted to the floating point random number.
    How is this conversion done and why does it yield a uniform distribution?

    How does one go about selecting a "good" seed?  I have seen the
    technique of using the low longword of the current system time
    many times.  However, I need to produce N pseudorandom numbers
    that will remain the same from run to run.  These numbers will
    eventually be used as seeds for further random number generation.
    I.e., I am trying to use MTH$RANDOM itself to generate good seeds!

            Rico
================================================================================
Note 271.1                         MTH$RANDOM                             1 of 3
ENGINE::BUEHLER "64% Br... Dead"                     14 lines  30-JUN-1987 10:07
--------------------------------------------------------------------------------

>    However, I need to produce N pseudorandom numbers
>    that will remain the same from run to run.

  You seem to have sufficient understanding of MTH$RANDOM to realize that
giving the same seed produces the same series of 'random' numbers.  Pick
a seed from thin air (say, 15) and get your N random numbers that you'll
be using as seeds.  By using 15 every time, you'll get the same random numbers
every time.  I'm not sure why you would want to do this, but this is one
way of doing it.  If the number of random seeds that you want is reasonably
limited, just create a precalculated table and stuff it into your image.

  If all this is obvious, my apologies.

John
================================================================================
Note 271.2                         MTH$RANDOM                             2 of 3
QUARK::LIONEL "We all live in a yellow subroutine"   13 lines  30-JUN-1987 11:21
--------------------------------------------------------------------------------

    MTH$RANDOM is an example of what I think are called "multiplicative
    congruential" number generators.  Given a good enough seed, the
    numbers are fairly uniform over the distribution, but if you start
    with a seed that has very few bits in it (like 15), you'll get
    worse numbers for the first few cycles.
    
    Conventional wisdom says to pick a seed that is large relative to
    the seed interval, and which is odd.  I like taking the middle
    32-bits of the system date-time, and forcing the low bit on.
    
    You might get a better discussion in the CLT::MATH conference.
    
    					Steve
================================================================================
Note 271.3                         MTH$RANDOM                             3 of 3
SQM::RICO                                            33 lines  30-JUN-1987 14:27
                                 -< more info >-
--------------------------------------------------------------------------------

    To give a little more info for the benefit of .1 and .2 (thanks
    for the replies), I want to generate thousands of random numbers,
    one for each of each of thousands of "processes", each of which will
    be used as a seed value for random number generation done by the
    process.

    The current method is to use 100000 as a seed and just generate
    N values between 0 and 10000.  This is a poor choice since the
    low seed values dispose the first random number generated as
    always being low.

    I could make a static table of "good" seeds.  The problem is,
    I don't want to generate thousands of numbers by hand.
    I could do things based on system time, however the sequence
    generated MUST remain the same from run to run for reasons I
    won't go into.  I could implement a static table just once by
    using the system time from whenever it happens to run and setting
    all the LSBs to make sure the seeds are odd.  This method just plain
    doesn't suit my fancy.  With my luck Murphy's Law of Synchronicity
    would generate me this horrible sequence of seeds that defy all
    the tips for "good seeds" that everybody has.

    My gut feeling is to just pick a "good" seed (a large prime
    I have been advised) to generate the numbers, and normallize
    them all to be in the range 0 to 2^32-1, i.e. the full range
    of values that a longword can take on.  But then I hear people
    say that "even numbers are not good seeds" and other such stuff
    that makes me wonder.  But I figure that if I let the seeds
    cover the range of all their possible values, I am taking
    proper precautions.  If there are still problems, it indicates
    a particularly weak random number generation algorithm.

            Rico

See note 531 (specifically .9 regarding MTH$RANDOM)

-Mike

The latest issue of ACM SIGPLAN monthly has an article recommending a 
'minimum standard' random number generator, that would be portable to many 
environments. Since the math libraries for many systems contain poor 
routines, the article is worth reading if you need to know this sort of
thing. 

Lynn Yarbrough 

RE: .2 (Lynn)
    
    I believe you meant the October 1988 issue of Communications of
    the ACM rather than SIGPLAN (unless there is one there too).  The
    Communications article is quite good, although their dismissal of
    alternatives to what they term "Lehmer" generators (prime modulus
    multiplicative congruential generators) is so rapid as to be
    invisible -- i.e., they just assume that nothing else is good enough.
    (Minor nit in justifying using the term Lehmer generators they
    refer to the "proper" name for them as "prime modulus multiplicative
    linear congruential generators" which seems to be deliberately
    padded out to better justify their term.  The "multiplicative"
    implies the "linear").
    
    They recommend a particular multiplier 16807 with modulus 2^31-1
    as a standard, in large part because theory shows that it is
    "pretty good" and it has been used alot.  However, in their
    words: "Our guess i sthat at some future point we will switch
    to either a=48271 ... or a=69621.  We are still awaiting the results
    of further testing and the accumulation of favorable user experience."
    The reason is that these two multipliers have much better "randomness"
    properties, and are equal in all other properties.  In other words,
    they are recommending what they know is likely to be an inferior
    "standard" and which will be difficult to supercede later (particularly
    since this statement is buried in the "theory" section which will
    be skipped over by many "practically oriented" readers).  They
    are discouraging the "user experience" needed, and possibly
    permanantly saddling us with less-than-ideal generators justified
    by reference to their article.  They should have put, all three
    candidates for multiplier in their initial recommendations with
    a description of the reasons for choosing one or the other.
    
    Additionally, for those who are so concerned with getting random
    number generating "right" they were rather lax in not specifying
    the limits of linear congruential generators.  That they should
    not be used by themselves in any application which has high
    dimensionality (i.e., uses n-tuples where n is large) or which
    is likely to be sensitive to slight correlations between adjacent
    values.
    
    					Topher
    

    I read the article, too.  It was a needed article but had shortcomings,
    as noted earlier.  In particular, the authors "evaluated" a number
    of standard generators and found most of them wanting.  Yet they
    failed to say anything about MTH$RANDOM.  Given that they discussed
    other systems (would you believe PRIMOS?), it seems a bit on the
    sloppy side to slight VMS.  Especially if MTH$RANDOM is inadequate,
    as it surely must be by their standards.
    
    I wonder who picked the coefficients for MTH$RANDOM?
    
    How much demand is there for a "better" VMS random number facility?

      John

>    How much demand is there for a "better" VMS random number facility?
    
    In theory, the demand for better random number generators is increasing --
    computers are getting fast enough that a cylce length of 2^32 isn't enough, 
    and double-precision random numbers are also becoming more important.
    
    In practice (I'm told) most large projects that depend heavily on random
    numbers develop their own RNGs.  This has a couple advantages:  It means
    they can choose different RNGs at link-time, without paying the cost of
    dispatching to the desired RNG at run-time;  They aren't limited to
    the performance/size constraints imposed by a general-purpose RNG;  They
    can fairly easily use several different streams of RNGs within the same
    application;  They can also substitute a 'cryptographically secure' RNG
    (which is still prohibitively expensive for a general-purpose RNG) if
    that's what the application requires.
    
    A few years ago, some work was done in DEC to find a better RNG, but it
    didn't provoke any changes or additions to the RNGs provided by DEC's O/Ses.

One of the joys of working with 32-bit arithmetic is that the largest prime 
< 2^31 happens to be 2^31-1, so using that as the prime modulus in a linear
congrential RNG provides the maximum possible period for that word size.
With other word lengths the situation is less convenient. 

For a 64-bit word length the maximum period is provided by the largest 
prime < 2^63, which is 2^63 - 25 = 9223372036854775783. Other primes in the 
vicinity are:
	  i	2^63-i
	 25	9223372036854775783
	165	9223372036854775643
	259	9223372036854775549
	301	9223372036854775507
	375	9223372036854775433
	387	9223372036854775421
	391	9223372036854775417

Another useful modulus for 64-bits might be the prime 
	2^61-1 = 2305843009213693951
which is reasonably large and also just a sequence of 1's. A RNG based on 
this modulus would have 1/4 the period of 2^63-25, but might run a bit
faster.