Random number generator

[Tom Wilson]

In article <1989Dec26.164103.17945 at ncsuvx.ncsu.edu> harish at ecebucolix.ncsu.edu writes:
>A lot of netters have suggested using  "rand = rand1*655536 + rand2" to
>create a uniform
>random number, where rand1 and rand2 are two uniform r.v's.  It should
>be noted that
>rand will NOT be uniform, since, if
>
>	z = a1*X + a2*Y , 
>
>then
>
>       pdf(z) = (a1*pdf(X)) *** (a2*pdf(Y)).
>
>Here *** denotes convolution, X and Y are independent random variables
>and pdf() is the probability
>density function.
>
>If pdf(X) and pdf(Y) are uniform, then pdf(z) is a trapezoid,
>degenerating to a triangular
>pdf if pdf(X) = pdf(Y), with a1 = a2.

>harish pu. hi.					harish at ecebucolix.ncsu.edu
>						harish at ecelet.ncsu.edu

I am wiling to accept your analysis for two continuous pdf's.  However, in the
case being considered here, rand1 and rand2 are uniform discrete distributions
on [0 .. 65535] (note 65535 = 2^16-1, a bit pattern of all 1s in a 16-bit
integer).  Then rand1*65536 + rand2 is the same as shifting rand1 left by
16 bits and or'ing rand2 into the lower 16 bits.  For each integer in 
[0 .. 65536^2 -1 ], there is a unique way that it can arise from this sum.
So it seems to me that P(k) = (1/65536)^2 for k in [0..65536^2-1],
because the two underlying terms each occur with P = 1/65536; therefore, it
is a uniform random distribution on the 32-bit integers.  

In general, we are looking at the very special case of two discrete 
uniform distributions on [0..n-1], and forming the new distribution
rand = n*rand1 + rand2.

Another thought:  this can be viewed not as a sum, but as picking
a coordinate in [0..65535] x [0..65535] using the two independent uniform
random variables.  The mapping from this rectangular region to [0..65536^2-1]
is 1-1 and onto, so the resulting distribution is uniform.


-- 
Tom Wilson                        wilson at uhccux.uhcc.Hawaii.Edu (Internet)
                                  wilson at uhccux.UUCP || wilson at uhccux (Bitnet)