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

[Ganesh Ajjanagadde]

On Fri, Mar 11, 2016 at 3:10 AM, Reimar Döffinger
<Reimar.Doeffinger at gmx.de> wrote:
> On 11.03.2016, at 05:16, Ganesh Ajjanagadde <gajjanag at gmail.com> wrote:
>> Code taken from the Julia project, licensed under MIT:
>> https://github.com/JuliaLang/julia/blob/master/base/random.jl, in turn
>> derived from: "The Ziggurat Method for generating random variables" - Marsaglia and Tsang.
>>
>> Paper and reference code: http://www.jstatsoft.org/v05/i08/. This is
>> well known to be the fastest method empirically for generating normal random
>> variables. Note that there are a large number of implementations with
>> various tunings, this was one of the simpler ones and also has a friendly
>> license.
>
> I absolutely can't see how this could be the fastest considering it uses the rather slow av_lfg_get twice, unless you only mean the part of getting floats in a certain distribution and not the actual randomness.

That is what I meant, all random generators use a uniform bitstream at
their core regardless and then transform it somehow. For example, the
linked arxiv paper (fastest I could fine) uses a SIMD optimized
Mersenne twister variant.

> I asked a long time ago for the decoder, but never got an answer why we use lfg and not a much faster lcg.

I guess there is no inherent reason.
I recall Michael's general analysis:
http://guru.multimedia.cx/category/pseudo-random-number-generators/.

> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel at ffmpeg.org
> http://ffmpeg.org/mailman/listinfo/ffmpeg-devel