PRNG proposal

[Matthew Woehlke]

Hmm. After playing with this some more, I noticed that the current 
algorithm has some... curious distribution characteristics.

First, what I did to the test program. Compared to the previous version, 
it is again generating RGB noise (i.e. using 24 bits of the 64 bits 
generated). The histogram is also now a 256x256 image where the pixel's 
blue value represents the relative occurrence of a 16-bit value. (A red 
pixel shows values with relative frequency within about 1% of the peak, 
green pixels show values with relative frequency less than 25%, with 
darker being closer to 25% and lighter being closer to 0.) The ideal 
would be solid red, representing a perfectly uniform distribution (i.e. 
all numbers occur equally).

So. One obvious problem is that a float-based algorithm cannot directly 
generate 64 random bits, since there are only 47 available in the 
mantissa. (This is evidenced by the obvious green bands in the histogram 
until the shift is increased to at least 9, to discard the "missing" / 
"fuzzy" bits.) More troubling however is the behavior displayed in the 
shift ranges around 35-50. Specifically, it looks like one or more of 
the mid-high bits are systemically zero. Perhaps this is related to my 
FPU, but at best it merely reinforces why not to use a fp-based PRNG.

Then of course there is the overall distribution, which is far from 
uniform. This could probably be argued either way, though personally I 
think a uniform distribution is preferable.

I'd like to see an integer-based PRNG with near-uniform distribution 
across any cross-section of bits. Bonus points if it generates 64 useful 
bits. I *think* my latest attempt satisfies that, but other suggestions 
are welcome. At this point I'm more concerned with the potential 
problems I've seen in the current implementation (that it can generate 
visual artifacts for certain initial conditions, that the distribution 
is non-uniform, and the behavior described above makes me nervous also).

-- 
Matthew
Please do not quote my e-mail address unobfuscated in message bodies.
-- 
このテキストを翻訳する時間の無駄だばかばかしい
-------------- next part --------------
A non-text attachment was scrubbed...
Name: noise.cpp.gz
Type: application/x-gzip
Size: 10032 bytes
Desc: not available
Url : http://mail.kde.org/pipermail/kimageshop/attachments/20081223/466db98c/attachment.gz