Re: [FWP] Shufflebug

[abigail@delanet.com]

On Tue, Jul 18, 2000 at 09:43:19AM -0700, Randal L. Schwartz wrote:
> 
> Neither.  With only 2^32 starting points for srand(), there's no
> sequence of steps that can give you more.  Your only option is to get
> *more* random bits from somewhere outside rand(), by reseeding between
> shuffles with something like Math::TrulyRandom.
> 
> Note that even the Fisher-Yates shuffle that uses a pure rand()
> solution will not generate fair decks.  You need to re-seed roughly
> every 32/6 calls to rand (right Abigail?).

Well, yes. Back in 1974, at the COMPSTAT conference in Vienna, Salfi
already pointed out that if a random generator is used whose value is
solely based on the value of the previous outcome (and that's true for
linear congruential methods), the output of a shuffle depends on exactly
three things: the shuffling algorithms being used, the initial state of
the thing to be shuffled, and the seed of the random generator.

Hence, assuming you use the same algorithm to all your shuffles, and
you always start with the deck in the same order (for instance, sorted),
there will be at most 2^32 different decks that can be dealt. (Note that
you can be truely unlucky and have far less different decks). And compared
to the number of permutations of a deck of cards, 2^32 is surprisingly
low. Even applying the shuffling algorithm on a deck of 13 cards will
not yield all different possible shuffles.

Repeatedly shuffling doesn't increase the number of different permutations
you can get. After all, a repeat shuffle is just a different algorithm, and
each algorithm is subject to the 2^32 upper bound. Even randomly picking
a shuffling algorithm from 2^32 different shuffling algorithms doesn't help.

You could of course take the output of a previous shuffle as input for the
next shuffle. Depending on the shuffling algorithm, you might get more than
2^32 different decks after doing many shuffles. However, for each shuffle,
there are only at most 2^32 different outcomes.

>                                         You need to re-seed roughly
> every 32/6 calls to rand (right Abigail?).

No. You will have to reseed after *EVERY CALL*. Think about it. It'll
be impossible for rand() to get the same outcome twice in a row (if it
would, it would never get anything else). But for a truely random (but
finite precision) generator, getting the same outcome twice in a row
has to be possible.

> Maybe there should be a version of rand() that "knows" when the
> entropy has been used up, and calls Math::TrulyRandom or Crypt::Random
> to reset.

Entropy is a red herring here. There is *NO* entropy in rand(). Given
the current state, the entire sequence of outcomes is predictable. You
would simply have to replace rand() with Math::TrulyRandom.


Don't forget to look up what Knuth has to write about all of this!



Abigail

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe