{"history":[],"article":{"id":"48b6ee46-1af9-4d5d-ba7d-a553c0f0e92b","title":"Marsaglia polar method","slug":"marsaglia-polar-method","content":":::summary\n:::\n\n# \nThe **[Marsaglia](https://bliptext.com/articles/george-marsaglia) polar method** is a [pseudo-random number sampling](https://bliptext.com/articles/pseudo-random-number-sampling) method for generating a pair of independent [standard normal random variables](https://bliptext.com/articles/standard-normal-random-variable).\nStandard normal random variables are frequently used in [computer science](https://bliptext.com/articles/computer-science), [computational statistics](https://bliptext.com/articles/computational-statistics), and in particular, in applications of the [Monte Carlo method](https://bliptext.com/articles/monte-carlo-method).\nThe polar method works by choosing random points (x, y) in the square −1 < x < 1, −1 < y < 1 until\nand then returning the required pair of normal [random variables](https://bliptext.com/articles/random-variable) as\nor, equivalently,\nwhere x/\\sqrt{s} and y/\\sqrt{s} represent the [cosine](https://bliptext.com/articles/co[sine](https://bliptext.com/articles/sine)) and [sine](https://bliptext.com/articles/sine) of the angle that the vector (x, y) makes with x axis.\n\n# Theoretical basis\nThe underlying theory may be summarized as follows:\nIf u is uniformly distributed in the interval\n0 ≤ u < 1, then the point\n(cos(2πu), sin(2πu))\nis uniformly distributed on the unit circumference\nx2 + y2 = 1, and multiplying that point by an independent\nrandom variable ρ whose distribution is\nwill produce a point\nwhose coordinates are jointly distributed as two independent standard\nnormal random variables.\n\n# History\nThis idea dates back to [Laplace](https://bliptext.com/articles/pierre-simon-laplace), whom [Gauss](https://bliptext.com/articles/carl-friedrich-gauss) credits with finding the above\nby taking the square root of\nThe transformation to polar coordinates makes evident that θ is uniformly distributed (constant density) from 0 to 2π, and that the\nradial distance r has density\n(r2 has the appropriate [chi square](https://bliptext.com/articles/chi-squared-distribution) distribution.)\nThis 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,\n\n# Practical considerations\nA direct application of this idea,\nis called the [Box–Muller transform](https://bliptext.com/articles/box-muller-transform), in which the chi variate is usually\ngenerated as\nbut that transform requires logarithm, square root, sine and cosine functions.\nOn some processors, the cosine and sine of the same argument can be calculated in parallel using a single instruction.\nNotably for Intel-based machines, one can use fsincos assembler instruction or the expi instruction (available e.g. in D), to calculate complex\nand just separate the real and imaginary parts.\n**Note:**\nTo explicitly calculate the complex-polar form use the following substitutions in the general form,\nLet and Then\nIn contrast, the polar method here removes the need to calculate a cosine and sine.\nInstead, by solving for a point on the unit circle, these two functions can be replaced with the x and y coordinates normalized to the radius.\nIn particular, a random point (x, y) inside the unit circle is projected onto the unit circumference by setting s=x^2+y^2 and forming the point\nwhich is a faster procedure than calculating the cosine and sine.\nSome 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.\nAlso this procedure requires about 27% more evaluations of the underlying random number generator (only of generated points lie inside of unit circle).\nThat random point on the circumference is then radially projected the required random distance by means of\nusing the same s because that s is independent of the random point on the circumference and is itself uniformly distributed from 0 to 1.\n\n# Implementation\n\n## Python\nA simple implementation in [Python](https://bliptext.com/articles/python-programming-language):\n\n## Java\nSimple implementation in [Java](https://bliptext.com/articles/java-programming-language) using the mean and standard deviation:\n\n## C++\nA non-[thread safe](https://bliptext.com/articles/thread-safe) implementation in [C++](https://bliptext.com/articles/c) using the mean and standard deviation:\n[C++11](https://bliptext.com/articles/c-11) GNU GCC [libstdc++](https://bliptext.com/articles/libstdc)'s implementation of std::normal_distribution [uses](https://bliptext.com/articles/undefined) the Marsaglia polar method, as quoted from [herein](https://bliptext.com/articles/undefined).\n\n## Julia\nA simple [Julia](https://bliptext.com/articles/julia-programming-language) implementation: The for loop can be parallelized by using the macro.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-26T09:36:29.823Z","updated_at":"2025-01-26T09:36:29.823Z","search_vector":"'marsaglia':1 'method':3 'polar':2","search_content":" \n \n\n# \nThe **[Marsaglia](https://bliptext.com/articles/george-marsaglia) polar method** is a [pseudo-random number sampling](https://bliptext.com/articles/pseudo-random-number-sampling) method for generating a pair of independent [standard normal random variables](https://bliptext.com/articles/standard-normal-random-variable).\nStandard normal random variables are frequently used in [computer science](https://bliptext.com/articles/computer-science), [computational statistics](https://bliptext.com/articles/computational-statistics), and in particular, in applications of the [Monte Carlo method](https://bliptext.com/articles/monte-carlo-method).\nThe polar method works by choosing random points (x, y) in the square −1 < x < 1, −1 < y < 1 until\nand then returning the required pair of normal [random variables](https://bliptext.com/articles/random-variable) as\nor, equivalently,\nwhere x/\\sqrt{s} and y/\\sqrt{s} represent the [co[sine](https://bliptext.com/articles/sine)](https://bliptext.com/articles/co[sine](https://bliptext.com/articles/sine)) and [sine](https://bliptext.com/articles/sine) of the angle that the vector (x, y) makes with x axis.\n\n# Theoretical basis\nThe underlying theory may be summarized as follows:\nIf u is uniformly distributed in the interval\n0 ≤ u < 1, then the point\n(cos(2πu), sin(2πu))\nis uniformly distributed on the unit circumference\nx2 + y2 = 1, and multiplying that point by an independent\nrandom variable ρ whose distribution is\nwill produce a point\nwhose coordinates are jointly distributed as two independent standard\nnormal random variables.\n\n# History\nThis idea dates back to [Laplace](https://bliptext.com/articles/pierre-simon-laplace), whom [Gauss](https://bliptext.com/articles/carl-friedrich-gauss) credits with finding the above\nby taking the square root of\nThe transformation to polar coordinates makes evident that θ is uniformly distributed (constant density) from 0 to 2π, and that the\nradial distance r has density\n(r2 has the appropriate [chi square](https://bliptext.com/articles/chi-squared-distribution) distribution.)\nThis 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,\n\n# Practical considerations\nA direct application of this idea,\nis called the [Box–Muller transform](https://bliptext.com/articles/box-muller-transform), in which the chi variate is usually\ngenerated as\nbut that transform requires logarithm, square root, sine and cosine functions.\nOn some processors, the cosine and sine of the same argument can be calculated in parallel using a single instruction.\nNotably for Intel-based machines, one can use fsincos assembler instruction or the expi instruction (available e.g. in D), to calculate complex\nand just separate the real and imaginary parts.\n**Note:**\nTo explicitly calculate the complex-polar form use the following substitutions in the general form,\nLet and Then\nIn contrast, the polar method here removes the need to calculate a cosine and sine.\nInstead, by solving for a point on the unit circle, these two functions can be replaced with the x and y coordinates normalized to the radius.\nIn particular, a random point (x, y) inside the unit circle is projected onto the unit circumference by setting s=x^2+y^2 and forming the point\nwhich is a faster procedure than calculating the cosine and sine.\nSome 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.\nAlso this procedure requires about 27% more evaluations of the underlying random number generator (only of generated points lie inside of unit circle).\nThat random point on the circumference is then radially projected the required random distance by means of\nusing the same s because that s is independent of the random point on the circumference and is itself uniformly distributed from 0 to 1.\n\n# Implementation\n\n## Python\nA simple implementation in [Python](https://bliptext.com/articles/python-programming-language):\n\n## Java\nSimple implementation in [Java](https://bliptext.com/articles/java-programming-language) using the mean and standard deviation:\n\n## C++\nA non-[thread safe](https://bliptext.com/articles/thread-safe) implementation in [C++](https://bliptext.com/articles/c) using the mean and standard deviation:\n[C++11](https://bliptext.com/articles/c-11) GNU GCC [libstdc++](https://bliptext.com/articles/libstdc)'s implementation of std::normal_distribution [uses](https://bliptext.com/articles/undefined) the Marsaglia polar method, as quoted from [herein](https://bliptext.com/articles/undefined).\n\n## Julia\nA simple [Julia](https://bliptext.com/articles/julia-programming-language) implementation: The for loop can be parallelized by using the macro.","revisionCount":0},"hasMore":false,"nextCursor":null}