Marsaglia polar method

The polar method of Marsaglia George and Thomas A. Bray is a method for generating normally distributed random numbers ( random number generator ).

History

This method goes back to the Box-Muller algorithm for generating normally distributed random variables. The starting point is a uniformly distributed point in the plane. In the Box-Muller algorithm, the Euclidean coordinates are utilized. In the method, these polar Euclidean coordinates are converted to polar coordinates. This saves you here the evaluation of trigonometric functions.

Description

With this method, two normally distributed random numbers are generated from two uniform random numbers:

The point must lie within the unit circle (), and it must be true, because in the real numbers, the logarithm of zero, and division by zero is not defined. In other circumstances, two new numbers and are generated.

By linear transformation thereof can be any normally distributed random numbers generate: the generated values ​​are - distributed, thus providing values ​​- are distributed.

Implementation

Pseudocode

Procedure Generate normally distributed random numbers ( reference parameters x1, x2)    Repeat      u = 2 * random number - 1 / / " random number " provides in [0,1)      v = 2 * random number - 1 / / uniformly distributed values      q = u * u v * v    Until (0 < q) and (q <1)    p = sqrt (-2 * ln ( q) / q)    x1 = u * p    x2 = v * p / / return by reference parameters x1, x2 end C

Double random (); / / Returns random numbers in the interval [0,1)   void polar ( double * x1, double * x2) {     double U, V, q, p;     do {        u = 2.0 * random () - 1;        v = 2.0 * random () - 1;        q = u * u v * v;     } While ( q == 0.0 | | q > = 1 );       p = sqrt (-2 * log ( q) / q);     * x1 = u * p;     * x2 = v * p; } The random () function is a function that displays a random integer in the interval [ 0; 1] returns.