Warp <war### [at] tagpovrayorg> wrote:
> Tim Attwood <tim### [at] anti-spamcomcastnet> wrote:
> > for example mersenne twister (MT19937) is seeded from
> > a single 32 bit value
>
>   If that's true, then IMO that lessens the usefulness of MT.
>
>   The RNG I'm considering supports very large seeds (up to something like
> 8192-bit seeds if so configured) and has very high quality and speed.
>
> --
>                                                           - Warp

Actually, most common *implementations* of the Mersenne Twister use a single
32-bit value to seed the generator. In actuality, the "seed" of the Mersenne
Twister can be any 2^19937 bit value, except all 1 bits. In practice, we use a
single 32-bit value to "randomly" generate the seed, where the "random" part is
usually an LCG. Some specific implementations do allow seeding the with the full
range of valid seeds. The method of seeding is a separate issue from whether the
MT is a good RNG.

In practice, you're going to want a simple seeding system that uses a single
32-bit value, for people who just need data that "looks" as random as possible.
Then you will want a full-range seeding system (such that it places the RNG
anywhere in its period), for people who need data that IS as random as
possible.

For raytracing, I'll venture a guess that 99.9% or more of our users just need
data that LOOKS as random as possible. Very few people need data that truly IS
as random as possible. The distinction is subtle.

Consider shuffling a deck of cards. Each time we shuffle the deck, use a truly
random process to determine the shuffling, like thermal noise or radioactive
decay or whatever. This is basically what happens when you seed a high quality
RNG. Regardless of how you seed the RNG, as long as the seed is essentially
random, the output will be completely random for most practical purposes.

So, back to the card shuffling example: Do this 16 times, to get 2^4 (most
likely) different shufflings of the deck. (I'm using 2^4 to help exaggerate the
problem of insufficient seed space.)

Now consider each of these 16 shufflings as corresponding with a particular
"seed" in the range 0 to (2^4)-1. Each of these 2^4 shuffled decks appears
completely random, because they ARE completely random (remember, the thermal
noise or whatever?). Any one of these would be fine, if all we want is a
raytraced image of a poker game or whatever, one that LOOKS random.

However, there are only 16 possible shufflings out of 52!, or about 8*10^67. So
not every possible shuffling can be acheived from our initial seeds. Not even
close!

But in reality, every possible shuffling could appear from a truly random
process. So the 2^4 seeds are not sufficient to provide a poker hand that comes
from a proper random distribution. It LOOKS completely random, if all you want
is something that "looks" like a random shuffling of a deck. But, for example,
if none of those 16 shuffled decks contains a royal flush for some player, then
no matter how you seed the RNG, no one will EVER get a royal flush.

In other words, if I'm a poker player with money on the line, then I want a game
that guarantees that every possible shuffle of the deck is possible. With only
16 seeds, then the game can only guarantee that the deck will be one of 16
pre-determined random shufflings of the deck. Like I said, the distinction is
subtle, and I suppose some people won't think the distinction matters at all.

Post a reply to this message