Re: Random Number Generation

[stt@houdini.camb.inmet.com (Tucker Taft)]

Dr J Parker (jp3@rl.ac.uk) wrote:
: Tucker Taft suggests: 

: "In any case, Ada.Numerics.Float_Random is the easiest one to adapt to your
: use, since it always generates values between 0.0 and 1.0.  You
: can then multiply that value by an appropriate integer or float
: and add the low bound to produce the desired dynamic range.

:   declare
:     Result : Integer range Low_Bound .. High_Bound;
:     Range_Length : constant Integer := High_Bound - Low_Bound + 1;
:   begin
:     Result := (Integer(Float(Range_Length) *
:       Ada.Numerics.Float_Random.Random(Gen)) mod Range_Length) + Low_Bound;
:     ...
: "


: Careful, there are some limits in which this fails. Simple example:
: Suppose you have a high quality random number generator R1 in the range
: 0 .. 127
: and you want to turn it into a high quality random number generator R2
: in the range 0 .. 82.
: Only the rejection method works: you must throw out at least
: 45 of the values returned by R1.  eg, if R1 returns a number in the range
: 83..127, then reject it and keep calling R1 until you get
: a number in the range 0 .. 82.  You'll get a stream of high quality random
: numbers in the range 0 .. 82.  In general, you reject just enough to make
: the number of elements (think bins) in range of R1 an integer multiple of
: the number of elements in the range of R2 (you reject never more than 50% of
: the number of elements in range of R1).  Then you
: can use "*"'s, etc to transform R1 into R2. Floating point doesn't
: change the problem.

I don't believe my suggestion suffers from the problem you fear.

The standard Float random number generator generates values uniformly
distributed from 0.0 to 1.0.  By multiplying these values by the number
of distinct integers wanted, and then (carefully) "pushing" them to a
neighboring exact integral value, you can get a uniform distribution
across any desired sequence of integers, provided the number of distinct
integers is significantly less than the period of the underlying generator.

The only trickiness above is that Ada rounds on conversion from float
to integer, so after multiplying by N and rounding to integer, you end 
up with 0 and N each occuring half as often as the values 1..N-1.  The
"mod" folds the N and 0 together, providing the desired uniform distribution
from 0 .. N-1, and then adding the low bound gives the desired low .. high
distribution.  If N is a very large number, on the order of the
underlying period of the Float random number generator, then clearly
the "uniformity" of the generator will not be as good, but provided
N << period, there is no need to use "rejection" to produce reasonable
uniformity.

-Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
Intermetrics, Inc.  Cambridge, MA  USA