[FFmpeg-devel] [PATCH] lavu/lfg: switch to Ziggurat algorithm for normal random number generation

[James Almer]

On 3/11/2016 1:16 AM, Ganesh Ajjanagadde wrote:
>  void av_bmg_get(AVLFG *lfg, double out[2])
>  {
> -    double x1, x2, w;
> -
> -    do {
> -        x1 = 2.0 / UINT_MAX * av_lfg_get(lfg) - 1.0;
> -        x2 = 2.0 / UINT_MAX * av_lfg_get(lfg) - 1.0;
> -        w  = x1 * x1 + x2 * x2;
> -    } while (w >= 1.0);
> -
> -    w = sqrt((-2.0 * log(w)) / w);
> -    out[0] = x1 * w;
> -    out[1] = x2 * w;
> +    out[0] = ziggurat(lfg);
> +    out[1] = ziggurat(lfg);
>  }
>  
>  #ifdef TEST
> diff --git a/libavutil/lfg.h b/libavutil/lfg.h
> index ec90562..6241359 100644
> --- a/libavutil/lfg.h
> +++ b/libavutil/lfg.h
> @@ -52,7 +52,7 @@ static inline unsigned int av_mlfg_get(AVLFG *c){
>  }
>  
>  /**
> - * Get the next two numbers generated by a Box-Muller Gaussian
> + * Get two numbers generated independently from a standard Gaussian distribution

I don't think a function called after Box-Muller Gaussian should suddenly
start using a different algorithm to generate random numbers.

How about adding a new av_ziggurat_get() or similarly named function for
this, and then replace av_bmg_get() usage where convenient?

>   * generator using the random numbers issued by lfg.
>   *
>   * @param out array where the two generated numbers are placed