Which algorithm to sample from the normal distribution $\mathcal{N}(0,1)$ is this

algorithmsnormal distributionprobabilityprobability distributionsprobability theory

This algorith, which takes a standard deviation and a mean, should sample from the normal distribution:

https://github.com/zama-ai/concrete/blob/5a12fb5b0196b48f1325a481dd8e3f4f04b710b6/concrete-core/src/backends/core/private/math/random/gaussian.rs#L19

Basically it looks like it does

s = u^2 + v^2; 
if (s>0 && s< 1) {
    cst = std * sqrt(-2&ln(s)/2); 
    output = (u*cst+mean, v*cst + mean); 
    break;
}

where u and v are random bytes.

I'm trying to know which algorithm is this and what is the greatest and smallest value it can output.

Best Answer

This is the Marsaglia polar method, a variant of the Box–Muller transform.

The very largest (and smallest) values of the result occur when the pair you're calling $(u,v)$ is as close to $0$ as possible. It looks like there is an option for a $32$-bit and $64$-bit version. With $b$ bits available, the smallest positive nonzero value is $1/2^{b-1}$ (this is then cast to a floating point value, which shouldn't cause problems). When $u = 1/2^{b-1}$ and $v = 0$, we get $s = 1/2^{2b-2}$; the final generated value (assuming a standard Gaussian) is $2\sqrt{(b-1)\ln 2}$. The most negative value should similarly be $-2\sqrt{(b-1)\ln 2}$.

This is about $9.27094$ for the $32$-bit version and about $13.2164$ for the $64$-bit version.