Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!think!ames!uhccux!wilson From: wilson@uhccux.uhcc.hawaii.edu (Tom Wilson) Newsgroups: comp.lang.c Subject: Re: Random number generator Message-ID: <5825@uhccux.uhcc.hawaii.edu> Date: 26 Dec 89 20:50:50 GMT References: <1989Dec24.175914.813@twwells.com> <83943@linus.UUCP> <940001@hpavla.HP.COM> <1989Dec26.164103.17945@ncsuvx.ncsu.edu> Reply-To: wilson@uhccux.UUCP (Tom Wilson) Organization: East-West Center, Honolulu Lines: 47 In article <1989Dec26.164103.17945@ncsuvx.ncsu.edu> harish@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@ecebucolix.ncsu.edu > harish@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@uhccux.uhcc.Hawaii.Edu (Internet) wilson@uhccux.UUCP || wilson@uhccux (Bitnet)