page_title: Box–Muller transform
section_title: Polar form
hierarchical_section_title: Box–Muller transform / Polar form
caption_attribution_description: Diagram to explain how the Box-Muller Transform can be expressed in polar coordinates in order to avoid using trigonometric functions in calculating it.
context_page_description: The Box–Muller transform, by George Edward Pelham Box and Mervin Edgar Muller, is a random number sampling method for generating pairs of independent, standard, normally distributed random numbers, given a source of uniformly distributed random numbers. The method was in fact first mentioned explicitly by Raymond E. A. C. Paley and Norbert Wiener in 1934.
  The Box–Muller transform is commonly expressed in two forms. The basic form as given by Box and Muller takes two samples from the uniform distribution on the interval [0, 1] and maps them to two standard, normally distributed samples. The polar form takes two samples from a different interval, [−1, +1], and maps them to two normally distributed samples without the use of sine or cosine functions.
  The Box–Muller transform was developed as a more computationally efficient alternative to the inverse transform sampling method. The ziggurat algorithm gives a more efficient method for scalar processors, while the Box–Muller transform is superior for processors with vector units. Furthermore, the Box–Muller transform can be employed for drawing from truncated bivariate Gaussian densities.
context_section_description: The polar form was first proposed by J. Bell and then modified by R. Knop. While several different versions of the polar method have been described, the version of R. Knop will be described here because it is the most widely used, in part due to its inclusion in Numerical Recipes.
  Given u and v, independent and uniformly distributed in the closed interval [−1, +1], set s = R² = u² + v². If s = 0 or s ≥ 1, discard u and v, and try another pair (u, v).  Because u and v are uniformly distributed and because only points within the unit circle have been admitted, the values of s will be uniformly distributed in the open interval (0, 1), too.  The latter can be seen by calculating the cumulative distribution function for s in the interval (0, 1).  This is the area of a circle with radius , divided by . From this we find the probability density function to have the constant value 1 on the interval (0, 1). Equally so, the angle θ divided by  is uniformly distributed in the interval [0, 1) and independent of s.
  We now identify the value of s with that of U₁ and  with that of U₂ in the basic form.  As shown in the figure, the values of  and  in the basic form can be replaced with the ratios  and , respectively.  The advantage is that calculating the trigonometric functions directly can be avoided.  This is helpful when trigonometric functions are more expensive to compute than the single division that replaces each one.
  Just as the basic form produces two standard normal deviates, so does this alternate calculation.
  and
caption: Two uniformly distributed values, u and v are used to produce the value s = R2, which is likewise uniformly distributed. The definitions of the sine and cosine are then applied to the basic form of the Box–Muller transform to avoid using trigonometric functions.
exif: {}