PRNG proposal

[Matthew Woehlke]

Cyrille Berger wrote:
> 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.

Some updates while my other reply is pending...

I went ahead and added a histogram view to the test program. It looks at 
8 bits at a time (you can choose any 8 consecutive bits). It looks like 
the worst-case for my algorithm is that the least-frequent number occurs 
about 75% as often as the most-occurring number (at least over the range 
I tested, which is both X and Y ranging from 0 to 512).

Contrast to the current algorithm, where 50% of the so-truncated results 
are either the maximum or minimum possible value with approximately 
equal probability, 25% are the next-to-min/max, and so on. (Apparently 
this is what is meant by "Gaussian distribution".)

I think it is actually contra-desirable for a PRNG's unmodified output, 
which would be another reason to change the algorithm while we still 
can. Especially since such output is trivially achieved by applying an 
additional mapping to the output. (In practice, I'd expect to use a 
tone-mapping filter if I wanted Gaussian noise as opposed to 
uniformly-distributed noise, with the additional note that such a step 
could be built into the generator.)

Code attached again (gzip'd this time so it doesn't fall into the 
moderation queue); you probably want the CMakeLists.txt from the 
still-pending message.

(Note: the '#if 0' currently enables the current krita implementation, 
change to '#if 1' for my current proposal.)

-- 
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 --------------
A non-text attachment was scrubbed...
Name: noise.cpp.gz
Type: application/x-gzip
Size: 9959 bytes
Desc: not available
Url : http://mail.kde.org/pipermail/kimageshop/attachments/20081222/67d0d69a/attachment.gz