PRNG proposal

[Matthew Woehlke]

Cyrille Berger wrote:
> On Tuesday 23 December 2008, Matthew Woehlke wrote:
>> Hmm. After playing with this some more, I noticed that the current
>> algorithm has some... curious distribution characteristics.
> 
> I hope you test it with a 32bits CPU ? otherwise it's kind of pointless... I 
> don't have to remind you that the origin of this discussion was because it 
> doesn't work with 64bits FPU...

I didn't, but isn't that the point; that it has weirdness on 64-bit 
CPU's? IMO an algorithm that is broken on some CPU's but not others is 
still broken :-). Perhaps even /more/ broken since it isn't consistent.

> Otherwise it was tested against some of the 
> characteristics of white noise, like I did for your first iteration of randum 
> number generator (the comment was wrong and probably a remain of the past 
> experiment).

I don't think I'm following that, sorry.

I made my own effort to examine the mean, and... except for the problem 
with the low-order bits showing visible tiling, I don't see a problem 
with that algorithm. Over a 1024x1024 region, I'm getting mean values 
right around 2^62, exactly where they should be. (I don't know that I 
can do standard deviation calculations without keeping an array of the 
values, but the histogram visually looks as good as can be expected. I'm 
also dropping the low 24 bits to have room to run an accumulator, but 
that should merely bias the mean a bit to the low end, not throw it off 
radically, and indeed I seem to be seeing just about the expected amount 
of bias toward zero.)

I've never used octave, but I wonder now how you came by your original 
results, as I apparently can't reproduce them. Or when you say "the 
comment was wrong", do you mean that you're not getting those results 
either?

Of course, I may or may not know what I'm doing, which is why I'd love 
to hear of your own results poking at my attempts. (I'm also not sure I 
know what you mean by "characteristics of white noise", to be honest.)

At any rate, my current preference is for the my latest generation (as 
attached) as it generates a full 64 bits of data, all of which seem to 
be adequate, or if that's too slow for the original algorithm I posted 
(either as-is, or with the expansion to a pure 64-bit version and with 
larger constants as in the alternate implementation, attached), probably 
reduced to a 48-bit output to strip the known-bad bits. Or for something 
better than we've come up with yet :-). If anyone has a better idea for 
a procedural PRNG, I'd love to hear about it.

My main complaints with the current one are that it relies on FPU quirks 
(I think we agree here :-) ) and that I'm really not thrilled with the 
Gaussian distribution (I'd prefer uniform).

-- 
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: 10265 bytes
Desc: not available
Url : http://mail.kde.org/pipermail/kimageshop/attachments/20081223/04c412c4/attachment-0001.gz