Re: Random number generation IP Sharp APL?
- From: "James J. Weinkam" <jjw@xxxxxxxxx>
- Date: Fri, 30 Jun 2006 03:17:16 GMT
Ibeam2000 wrote:
What you need to do is find something which varies wildly betweenThis is exactly the wrong thing to do.
executions. Often, it would be the milliseconds on []TS, but often you
can't even get that, depending on the granularity of the system's
clock. Set []RL to this number, and you should have more random random
numbers.
The built in random number generator in every APL implementation that I have
seen uses what is technically known as a linear congruential random number
generator to generate a sequence of random integers. These are then
transformed into whatever form is needed for the purpose at hand.
In general, in a linear congruential sequence, the next member of the sequence
is computed from the current member by the formula:
next {is} modulus | constant + multiplier {times} current
The initial value of current is called the seed. APL calls it the random link
{quad}RL.
The usual practice is to choose the modulus, constant, and multiplier so that
the resulting sequence(s) simultaneously have a long period and exhibit good
randomness properties. Usually this is done by choosing the modulus first,
then deciding whether or not to use a non zero constant, then picking from
among all multiplier (and constants if non zero) that yield the maximum
possible period, specific value(s) which pass a number of tests for
randomness. For most systems that have some sort of built in random number
generator all of this is hard wired into the system. The only control the user
has over the process is to choose the initial value (seed).
Exactly how the seed should be chosen and the consequences of particular
choices depend on the modulus and constant.
If the constant is non zero then the maximum achievable period is equal to the
modulus. I.e., all values between 0 and modulus-1 will occur in some order
before the sequence repeats. This maximum period can only be achieved under
the following conditions:
1. The constant and modulus must be relatively prime (i.e., have no common
factor other than 1).
2. Every prime divisor of the modulus must also be a divisor of multiplier-1
3. If 4 is a divisor of the modulus it must also be a divisor of multiplier-1
In this situation, all choosing the seed does is choose the starting point in
the one and only permutation of the integers 0...modulus-1 that the generator
produces.
If the constant is zero the maximum achievable period depends on the prime
factorization of the modulus and can be achieved under the following
conditions:
1. The seed and the modulus are relatively prime
2. The multiplier is a primitive modulo the modulus
In this situation, if the modulus is a prime, p, then the maximum period is p-1
and the seed, which can be any value between 1 and p-1 inclusive again simply
chooses the starting point in the one and only permutation of the integers
1...p-1 that the generator produces. On the other hand, if the modulus is
composite, then the choosing the seed selects not only the starting point but
also which of several disjoint sequences the generator produces. Moreover
choosing a seed which is nor relatively prime to the modulus causes the
generator to produce a subsequence which is not of maximum length.
From this you can see that unless you know quite a bit about the specific
random number generator you are using you have no business messing with the
seed at all. You could easily shoot yourself in the foot.
Why would one set the seed?
One reason is to ensure that exactly the same sequence of values is used on
separate occasions. This is useful in debugging.
A second reason is to ensure that several replications of an experiment are
done using independent sequences of random numbers. Now here is where picking
seeds out of the air is fraught with danger. You may well choose a seed for
the second experiment that simply gives the same sequence as was used in the
first experiment shifted by a few places. This will in general lead to a high
correlation between the two results instead of the desired independence. The
easiest way to avoid this pitfall is to simply continue using random numbers
from the same sequence without reseeding the generator for each replication.
If the replications must be done in separate runs, this can be achieved by
saving the value of the seed at the end or each run and using that value to
seed the generator at the start of the next run.
In some applications, in order to reduce the variance of the results, one wants
to have separate random number generators for various separate needs for random
values within the application. Say, for example, that you need four separate
random number streams. You achieve this by picking four seeds that are far
enough apart in the sequence produced by the underlying linear congruential
generator that the four sub sequences do not overlap. In APL terms, you would
then set and save {quad}RL before and after each use of {roll} or {deal}.
Obviously you can only do this if you come armed with a knowledge of the
parameters of the underlying linear congruential generator.
For the OS/2 version of APL2, a little experimentation reveals that
constant=0
modulus=2147483647, which is (2*31)-1, which is prime
multiplier=16807
initial {quad}RL=16807
I have no idea what values are used in other implementations of APL but it isn't hard to devise experiments to discover what values are being used.
.
- References:
- Random number generation IP Sharp APL?
- From: Fredric L. Rice
- Re: Random number generation IP Sharp APL?
- From: Ibeam2000
- Random number generation IP Sharp APL?
- Prev by Date: Re: Random number generation IP Sharp APL?
- Previous by thread: Re: Random number generation IP Sharp APL?
- Next by thread: []FMT usage question
- Index(es):
Relevant Pages
|
