karl@haddock.ISC.COM (Karl Heuer) (02/19/88)
Followups to sci.math; this has nothing to do with C anymore. >[A good approximation to a Gaussian distribution can be obtained by >generating about 12 independent random numbers uniformly from [0,1), adding >them together, and dividing by 12.] Actually, the reason for using 12 of them (not "about 12") is that you don't need to rescale. The variance of the uniform distribution is 1/12, so adding 12 of them gives you a distribution with variance 1. If you subtract 6, you then have a good approximation of a standard Gaussian. I happen to prefer the polar-coordinate version, because it's mathematically exact, requires only one call to the uniform RNG per result, and is faster (or so I've been told). Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint
mouse@mcgill-vision.UUCP (der Mouse) (03/10/88)
In article <2629@haddock.ISC.COM>, karl@haddock.ISC.COM (Karl Heuer) writes: > Followups to sci.math; this has nothing to do with C anymore. I'm redirecting them to comp.misc, because this has nothing to do with C specifically, but what I have to say is about computing results rather than the mathematical aspects of the question. >> [Approximating a Gaussian generator by adding 12 numbers in [0,1) >> and subtracting 6] > I happen to prefer the polar-coordinate version, because it's > mathematically exact, Of course, the probability of getting one of the values out in the tail of the proper Gaussian distribution is only one in several thousand. But I suppose if you're generating hundreds of thousands of them.... > requires only one call to the uniform RNG per result, As far as I can see, this affects only esthetics and possibly speed > and is faster (or so I've been told). I just ran a quick comparison. The uniform RNG was obtained by writing an assembly-language wrapper for 4.3BSD random(), the wrapper getting a float out of random() by dropping the random bits into the mantissa of a floating-point number and scaling to [0,1). The machine on which this was done is a VAX-11/750. Both Gaussian generators were hand-coded in assembly. The polar method was straight out of Knuth; the add-twelve-numbers was improvised on the spot (it was only about six instructions). I find that the polar method is about a factor of three faster. The measurements I got were 1079.84 calls/sec for the polar method (34220 calls took 3169 clock ticks of 1/100 second each) and 342.264 calls/sec for the twelve-number method (9070 calls in 2650 ticks). Of course, this was done on a multi-user system, but I did run it at nice -10, and made sure time taken to page things in didn't affect things much. If I really cared, I'd run it standalone. der Mouse uucp: mouse@mcgill-vision.uucp arpa: mouse@larry.mcrcim.mcgill.edu