[FFmpeg-devel] [PATCH] normal PRNG using ziggurat method

[Michael Niedermayer]

On Mon, Sep 08, 2008 at 11:04:48PM -0400, Justin Ruggles wrote:
> Michael Niedermayer wrote:
> > On Mon, Sep 08, 2008 at 08:05:34PM -0400, Justin Ruggles wrote:
> >> Hi,
> >>
> >> This is a patch to add a PRNG which generates numbers with standard
> >> normal distribution.  It uses the ziggurat method, which is quite fast
> >> compared to other methods.
> >>
> >> I was working on another implementation based on the original paper,
> >> which had sample code in it that I was using as a starting point.  Then
> >> I noticed the teeny tiny print at the bottom of the journal's download
> >> page which states that the code is under GPL... :(  I found another
> >> implementation which was based on the paper without using the
> >> accompanying code and is under a BSD-style license.  I trimmed it down,
> >> cleaned-up it up, and adapted it for FFmpeg.
> >>
> > 
> >> I need this for spectral extension processing in the E-AC-3 decoder.
> >> The spec requires that the generated noise which is blended with
> >> translated coeffs have "zero-mean, unity variance".
> > 
> > is "zero-mean, unity variance" everything the spec requires or is there
> > more?
> 
> That is all it requires.
> 
> > Because any signal (like the output of any PRNG) can be scaled and translated
> > to have that, there would be no need for normal distributed PRNG.
> > 
> > 
> > [...]
> 
> This does scale and translate output from one of the already existing
> PRNG's...sort of. :)
> 
> The zero mean part is easy enough.  If there is a simpler (and faster)
> way to generate random noise with unity variance distribution, please
> tell me.

well lets assume you have a PRNG that returns 32bit values between 
1-(1<<31) and (1<<31)-1 then its variance is

0x155555551555555580000000 / 0xFFFFFFFF

or
4611686016279904256 / 3

or
(2^62 - 2^31) / 3

if you want to have unit variance then you have to scale the output of the
PRNG by the inverse of the sqare root of above
that is
/ sqrt((2^62 - 2^31) / 3)
thats about
* .0000000008065490089227220965715845679045014243097423344385291291108274584648500175464441618401658093...


[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Many that live deserve death. And some that die deserve life. Can you give
it to them? Then do not be too eager to deal out death in judgement. For
even the very wise cannot see all ends. -- Gandalf
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20080909/03af08c7/attachment.pgp>