PRNG proposal
Matthew Woehlke
mw_triad at users.sourceforge.net
Tue Dec 23 18:56:43 CET 2008
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
More information about the kimageshop
mailing list