[comp.lang.c] Normal distribution random number generator -- WANTED

winarko@qucis.queensu.CA (Edi Winarko) (12/01/90)

I am looking for C source code to generate normal distribution
random numbers. I want to be able to generate random numbers
in the range of 0 - N (N could be equal to 9999, 99999 or 999999) that 
have normal distribution with mean, say, u and standard deviation s.

Thanks for any help,

--Edi W
winarko@qucis.queensu.ca

wilf@sce.carleton.ca (Wilf Leblanc) (12/01/90)

winarko@qucis.queensu.CA (Edi Winarko) writes:

>I am looking for C source code to generate normal distribution
>random numbers. I want to be able to generate random numbers
>in the range of 0 - N (N could be equal to 9999, 99999 or 999999) that 
>have normal distribution with mean, say, u and standard deviation s.

Add M random uniform random numbers x (where x is between 0 and
N/M).  Using M = 12 to 30, will generate random variables which
are very close to normal, (not quite, but your specification
of limits ensures the results will not 'truly' be normal).
This works because of the central limit theorem (see any
probability text).  The variance and mean are easily computable
from M and N.

I hope this helps.  If you want source code, mail me.

>Thanks for any help,

>--Edi W
>winarko@qucis.queensu.ca

--
---
Wilf LeBlanc                                Systems and Computer Eng.
Internet: wilf@sce.carleton.ca              Carleton University
    UUCP: ...!uunet!mitel!sce!wilf          Ottawa, Ont, Canada

brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (12/02/90)

In article <wilf.660026793@rigel.sce.carleton.ca> wilf@sce.carleton.ca (Wilf Leblanc) writes:
> >I am looking for C source code to generate normal distribution
> >random numbers.
> Add M random uniform random numbers x (where x is between 0 and
> N/M).  Using M = 12 to 30, will generate random variables which
> are very close to normal,

There are many methods available which are not only accurate but also a
lot faster than generating and summing thirty numbers. (It's also very
dangerous to add successive outputs of a linear congruential sequence.)
Look in Knuth chapter 3 to find some good techniques.

---Dan

adkins@iguana.cis.ohio-state.edu (Brian Adkins) (12/03/90)

>I am looking for C source code to generate normal distribution
>random numbers. I want to be able to generate random numbers
>in the range of 0 - N (N could be equal to 9999, 99999 or 999999) that 
>have normal distribution with mean, say, u and standard deviation s.

I'm not sure if this is exactly what you want, but the Box-Muller method
takes a pair of independent uniform variables ("regular random numbers") 
and creates a pair of standard normal variables:

   z1 = sqrt(-ln(u2)) * cos(2*PI*u1)
   z2 = sqrt(-ln(u2)) * sin(2*PI*u1)

where the angle is expressed in radians.  You probably can convert from 
standard normal variables to the specific case, but for completeness:

   x1 = u + s * z1,  x2 = u + s * z2   where u is mean, s is std. dev.

this method is almost universally preferred over solving for r = F(z)

most of this info is from "Probability & Statistics for Engineers" Miller...

wilf@sce.carleton.ca (Wilf Leblanc) (12/04/90)

adkins@iguana.cis.ohio-state.edu (Brian Adkins) writes:

>>I am looking for C source code to generate normal distribution
>>random numbers. I want to be able to generate random numbers
>>in the range of 0 - N (N could be equal to 9999, 99999 or 999999) that 
>>have normal distribution with mean, say, u and standard deviation s.

>I'm not sure if this is exactly what you want, but the Box-Muller method
>takes a pair of independent uniform variables ("regular random numbers") 
>and creates a pair of standard normal variables:

>   z1 = sqrt(-ln(u2)) * cos(2*PI*u1)
>   z2 = sqrt(-ln(u2)) * sin(2*PI*u1)

>where the angle is expressed in radians.  You probably can convert from 
>standard normal variables to the specific case, but for completeness:

>   x1 = u + s * z1,  x2 = u + s * z2   where u is mean, s is std. dev.

>this method is almost universally preferred over solving for r = F(z)

>most of this info is from "Probability & Statistics for Engineers" Miller...

Assume for a moment the mean (u) is zero and s is the standard deviation.
If N/s > 10 then the problem amounts to getting a good
normal random number generator which accurately models the tails of
the normal distribution.  i.e. if we are using 32 bit integers for
the uniform random number generator and u2 is non-zero (it must be)
then the maximum value of z1 or z2 is sqrt(-ln(min(u2))). If min(u2) is
1/2^31, then the maximum is sqrt(ln(2^31)) = 4.6.  (If min(u2) is 2^63,
the max is 6.6).

I guess the whole point is to use many bits in the random number generator
if you want to model the tails accurately.  In some applications, the tails
are very important.  One example is very, very low error rate digital
communications.  If you are not careful, you can easily get funny behavoir
in the tail of the distribution.

Maybe this wasn't really the original problem, but this is what I thought.

Is there a better way (rather than just adding many, many, uniform random
numbers) ?  I guess one could use the above formula, and add succesive
outputs (and scale of course).  If we were to add 16 consecutive normals,
(using the above algorithm) then divide by 4, we would obtain a more accurate
tail.

I usually use the above method, but my applications rarely require a very
accurate tail.
--
Wilf LeBlanc                          Carleton University
Internet: wilf@sce.carleton.ca        Systems & Computer Eng.
    UUCP: ...!uunet!mitel!sce!wilf    Ottawa, Ont, Canada, K1S 5B6

jrv@sdimax2.mitre.org (VanZandt) (12/11/90)

In article <86482@tut.cis.ohio-state.edu> Brian Adkins <adkins@cis.ohio-state.edu> writes:
>>I am looking for C source code to generate normal distribution
>>random numbers. 
>
>I'm not sure if this is exactly what you want, but the Box-Muller method
>takes a pair of independent uniform variables ("regular random numbers") 
                 ^^^^^^^^^^^
>and creates a pair of standard normal variables:
>...

If the two variables you start with are correlated, the resulting numbers
won't have a normal distribution.  Make sure you have a good RNG if you use
this method, or maybe discard a few numbers between the two you use.

                               - Jim Van Zandt

adkins@skink.cis.ohio-state.edu (Brian Adkins) (12/13/90)

>>I'm not sure if this is exactly what you want, but the Box-Muller method
>>takes a pair of independent uniform variables ("regular random numbers") 
>                 ^^^^^^^^^^^
>If the two variables you start with are correlated, the resulting numbers
>won't have a normal distribution.  Make sure you have a good RNG if you use

Well what do you think I mean when I say independent uniform variables?