PRNG proposal

[Matthew Woehlke]

Cyrille Berger wrote:
> Well unfortunately it doesn't seem to have nice white noise property:
> 
> I tried various seed, here is one example of the stat I got:
> mean =  9.2188e+18
> max =  1.8447e+19
> min = 3.4784e+13
> median =  9.2184e+18
> std =  5.3239e+18
> var =  2.8344e+37
> (mean - (max+min)/ 2) = -4.6155e+15
> 
> The two things I find worrying is the high median, it indicates that half the 
> values are in the range [ 9.2184e+18; 1.8447e+19] while the other half is 
> spread on [ 3.4784e+13; 9.2184e+18 ]. And in our case, the white noise 
> property concerning the mean would (mean - (max+min)/ 2) == 0. The hardest 
> white noise property to get right is the autocorrelation.

You seem to have a very specific notion of certain properties you are 
looking for! This is probably good, it means you are better able to 
judge "high quality" than I am.

Anyway, I suspect this is related to the constants being thrown to 
create the initial pseudo-random value, namely that they are still 
"relatively" small. I went back and tried some new, much larger numbers 
(btw these are all primes, not sure if that's a good thing or not).

I also tried a second variation that uses two slightly different 
formulas (and wholly different constants) for the initial permutation, 
and then incorporates a perlin-like static permutation table, using a 
combination of the two "salts" to twist the bits around. I /think/ this 
should generate a much more even distribution. At any rate, it has the 
nice property of generating noise that is visually random even in the 
low bits (the other implementation is still visually repeated in the low 
8 bits... rather badly so, in fact).

Eventually I'd like to try writing some histogram plots into this, but 
I'm not sure when I'd be able to get to that. Anyway, I'm attaching my 
test program (it shouldn't be overly hard to extract the generator 
function, but there are almost 400 lines of permutation tables, so I'm 
not going to inline it this time).

If you get a chance to throw you own tests at this, that would be 
awesome. (At some point, I suppose we should also try to run a 
performance comparison...)

To build, you'll want to comment out the other generators in the 
CMakeLists.txt :-).

-- 
Matthew
Please do not quote my e-mail address unobfuscated in message bodies.
-- 
This message represents the official view of the voices in my head.
   -- Unknown
(found at http://goldmark.org/jeff/stupid-disclaimers/fun.html)
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: noise.cpp
Url: http://mail.kde.org/pipermail/kimageshop/attachments/20081222/1def74b0/attachment-0001.bat 
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: CMakeLists.txt
Url: http://mail.kde.org/pipermail/kimageshop/attachments/20081222/1def74b0/attachment-0001.txt