# Marsaglia polar method

Jump to navigation Jump to search

The polar method (attributed to George Marsaglia, 1964[1]) is a pseudo-random number sampling method for generating a pair of independent standard normal random variables.[2] While it is superior to the Box–Muller transform,[3][4] the Ziggurat algorithm is even more efficient.[5]

Standard normal random variables are frequently used in computer science, computational statistics, and in particular, in applications of the Monte Carlo method.

The polar method works by choosing random points (xy) in the square −1 < x < 1, −1 < y < 1 until

${\displaystyle s=x^{2}+y^{2}<1,\,}$

and then returning the required pair of normal random variables as

${\displaystyle x{\sqrt {\frac {-2\ln(s)}{s}}}\,,\ \ y{\sqrt {\frac {-2\ln(s)}{s}}},}$

or, equivalently,

${\displaystyle {\frac {x}{\sqrt {s}}}{\sqrt {-2\ln(s)}}\,,\ \ {\frac {y}{\sqrt {s}}}{\sqrt {-2\ln(s)}},}$

where ${\displaystyle x/{\sqrt {s}}}$ and ${\displaystyle y/{\sqrt {s}}}$ represent the cosine and sine of the angle that the vector (x, y) makes with x axis.

## Theoretical basis

The underlying theory may be summarized as follows:

If u is uniformly distributed in the interval 0 ≤ u < 1, then the point (cos(2πu), sin(2πu)) is uniformly distributed on the unit circumference x2 + y2 = 1, and multiplying that point by an independent random variable ρ whose distribution is

${\displaystyle \Pr(\rho

will produce a point

${\displaystyle \left(\rho \cos(2\pi u),\rho \sin(2\pi u)\right)}$

whose coordinates are jointly distributed as two independent standard normal random variables.

## History

This idea dates back to Laplace, whom Gauss credits with finding the above

${\displaystyle I=\int _{-\infty }^{\infty }e^{-x^{2}/2}\,dx}$

by taking the square root of

${\displaystyle I^{2}=\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }e^{-(x^{2}+y^{2})/2}\,dx\,dy=\int _{0}^{2\pi }\int _{0}^{\infty }re^{-r^{2}/2}\,dr\,d\theta .}$

The transformation to polar coordinates makes evident that θ is uniformly distributed (constant density) from 0 to 2π, and that the radial distance r has density

${\displaystyle re^{-r^{2}/2}.\,}$

(r2 has the appropriate chi square distribution.)

This method of producing a pair of independent standard normal variates by radially projecting a random point on the unit circumference to a distance given by the square root of a chi-square-2 variate is called the polar method for generating a pair of normal random variables,

## Practical considerations

A direct application of this idea,

${\displaystyle x={\sqrt {-2\ln(u_{1})}}\cos(2\pi u_{2}),\quad y={\sqrt {-2\ln(u_{1})}}\sin(2\pi u_{2})}$

is called the Box Muller transform, in which the chi variate is usually generated as

${\displaystyle {\sqrt {-2\ln(u_{1})}},}$

but that transform requires logarithm, square root, sine and cosine functions. On some processors, the cosine and sine of the same argument can be calculated in parallel using a single instruction.[6] Notably for Intel-based machines, one can use fsincos assembler instruction or the expi instruction (available e.g. in D), to calculate complex

${\displaystyle {\text{expi}}(z)=e^{iz}=\cos(z)+i\sin(z),\,}$

and just separate the real and imaginary parts.

Note: To explicitly calculate the complex-polar form use the following substitutions in the general form,

Let ${\displaystyle r={\sqrt {-2ln(u_{1})}}}$ and ${\displaystyle z=2\pi u_{2}}$ then,

${\displaystyle \ re^{iz}={\sqrt {-2ln(u_{1})}}e^{i2\pi u_{2}}={\sqrt {-2ln(u_{1})}}\left[\cos(2\pi u_{2})+i\sin(2\pi u_{2})\right]}$.

In contrast, the polar method here removes the need to calculate a cosine and sine. Instead, by solving for a point on the unit circle, these two functions can be replaced with the x and y coordinates normalized to the ${\displaystyle {\sqrt {x^{2}+y^{2}}}}$ radius. In particular, a random point (xy) inside the unit circle is projected onto the unit circumference by setting ${\displaystyle s=x^{2}+y^{2}}$ and forming the point

${\displaystyle \left({\frac {x}{\sqrt {s}}},{\frac {y}{\sqrt {s}}}\right),\,}$

which is a faster procedure than calculating the cosine and sine. Some researchers argue that the conditional if instruction (for rejecting a point outside of the unit circle), can make programs slower on modern processors equipped with pipelining and branch prediction.[7] Also this procedure requires about 27% more evaluations of the underlying random number generator (only ${\displaystyle \pi /4\approx 79\%}$ of generated points lie inside of unit circle).

That random point on the circumference is then radially projected the required random distance by means of

${\displaystyle {\sqrt {-2\ln(s)}},\,}$

using the same s because that s is independent of the random point on the circumference and is itself uniformly distributed from 0 to 1.

## Implementation

Simple implementation in Java using the mean and standard deviation:

private static double spare;
private static boolean isSpareReady = false;

public static synchronized double getGaussian(double mean, double stdDev) {
if (isSpareReady) {
isSpareReady = false;
return spare * stdDev + mean;
} else {
double u, v, s;
do {
u = Math.random() * 2 - 1;
v = Math.random() * 2 - 1;
s = u * u + v * v;
} while (s >= 1 || s == 0);
double mul = Math.sqrt(-2.0 * Math.log(s) / s);
spare = v * mul;
isSpareReady = true;
return mean + stdDev * u * mul;
}
}


An implementation, not thread safe, in C++ using the mean and standard deviation:

 1 double generateGaussianNoise(const double& mean, const double &stdDev) {
2
3 	static bool hasSpare = false;
4 	static double spare;
5
6 	if(hasSpare) {
7 		hasSpare = false;
8 		return mean + stdDev * spare;
9 	}
10
11 	hasSpare = true;
12 	static double u, v, s;
13 	do {
14 		u = (rand() / ((double) RAND_MAX)) * 2.0 - 1.0;
15 		v = (rand() / ((double) RAND_MAX)) * 2.0 - 1.0;
16 		s = u * u + v * v;
17 	}
18 	while( (s >= 1.0) || (s == 0.0) );
19
20 	s = sqrt(-2.0 * log(s) / s);
21 	spare = v * s;
22 	return mean + stdDev * u * s;
23 }


C++11 GNU GCC libstdc++'s implementation of std::normal_distribution uses the Marsaglia polar method, as quoted from herein.

 1 if (_M_saved_available)
2 {
3     _M_saved_available = false;
4     ret = _M_saved;
5 }
6 else
7 {
8     result_type x, y, r2;
9     do
10     {
11         x = result_type(2.0) * aurng() - 1.0;
12         y = result_type(2.0) * aurng() - 1.0;
13         r2 = x * x + y * y;
14     }
15     while (r2 > 1.0 || r2 == 0.0);
16
17     const result_type mult = std::sqrt(-2 * std::log(r2) / r2);
18     _M_saved = x * mult;
19     _M_saved_available = true;
20     ret = y * mult;
21 }


## References

1. ^ Marsaglia, G.; Bray, T. A. (1964). "A Convenient Method for Generating Normal Variables". SIAM Review. 6 (3): 260–264. JSTOR 2027592.
2. ^ Peter E. Kloeden Eckhard Platen Henri Schurz, Numerical Solution of SDE Through Computer Experiments, Springer, 1994.
3. ^ Martino, L.; Luengo, D.; Míguez, J. (2012). "Efficient sampling from truncated bivariate Gaussians via Box-Muller transformation". Electronics Letters. 48 (24): 1533–1534. CiteSeerX 10.1.1.716.8683. doi:10.1049/el.2012.2816.
4. ^ Glasserman, Paul (2004), Monte Carlo Methods in Financial Engineering, Applications of Mathematics: Stochastic Modelling and Applied Probability, 53, Springer, p. 66, ISBN 9780387004518.
5. ^ Thomas, David B.; Luk, Wayne; Leong, Philip H.W.; Villasenor, John D. (2007). "Gaussian random number generators". ACM Computing Surveys. 39 (4): 11–es. CiteSeerX 10.1.1.127.5773. doi:10.1145/1287620.1287622.
6. ^ Kanter, David. "Intel's Ivy Bridge Graphics Architecture". Real World Tech. Retrieved 8 April 2013.
7. ^ This effect can be heightened in a GPU generating many variates in parallel, where a rejection on one processor can slow down many other processors. See section 7 of Thomas, David B.; Howes, Lee W.; Luk, Wayne (2009), "A comparison of CPUs, GPUs, FPGAs, and massively parallel processor arrays for random number generation", in Chow, Paul; Cheung, Peter Y. K., Proceedings of the ACM/SIGDA 17th International Symposium on Field Programmable Gate Arrays, FPGA 2009, Monterey, California, USA, February 22-24, 2009, Association for Computing Machinery, pp. 63–72, CiteSeerX 10.1.1.149.6066, doi:10.1145/1508128.1508139, ISBN 9781605584102.