Tuesday, December 13, 2011

Generating random numbers with normal distribution

Question: Given a standard generator with uniform distribution, generate a normally distributed sequence of random numbers.
Answer: Box-Muller transform!

http://en.wikipedia.org/wiki/Box%E2%80%93Muller_transform

Source snippet:

class NormalRandom
{
        private bool haveNextRandom = false;
        private  double nextRandom = 0;
        private  Random rnd = new Random();

        /// <summary>
        /// Implements random number generator with normal distribution
        /// based on the polar form of Box-Muller transform.
        /// </summary>
        /// <returns>A random number with normal distribution.</returns>
        public double NextDouble()
        {
            if (haveNextRandom)
            {
                haveNextRandom = false;
                return nextRandom;
            }

            double x1, x2, w;
            do
            {
                x1 = 2.0 * rnd.NextDouble() - 1.0;
                x2 = 2.0 * rnd.NextDouble() - 1.0;
                w = x1 * x1 + x2 * x2;
            } while (w >= 1.0);

            w = Math.Sqrt((-2.0 * Math.Log(w)) / w);
            nextRandom = x2 * w;
            haveNextRandom = true;

           return x1 * w;
        }
}

...and here are the results:

1 comment:

Georgii Kalnytskyi said...

There is another method, but less accurate. If you don't know about Box-Muller transformation you can use Central limit theorem and add about 12 random numbers and then divide them by their standard deviation.