Re: [FWP] Shufflebug

[merlyn@stonehenge.com (Randal L. Schwartz)]

>>>>> "Amir" == Amir Karger <karger@fermi2.chem.yale.edu> writes:

Amir> I know nothing about randomness.

Good, because this is pseudorandomness. :)

Amir>  So the questions:

Amir> (1) do you agree that this problem exists?

Yes.  srand() has only 2^32 input values (I think).

Amir> (2) do you agree with the fix? 

Amir> It seems clear that always doing 5 shuffles gives you exactly the same
Amir> number of permutations as doing 1 shuffle.

Yes.

Amir>  However, I can't work out whether
Amir> randomly doing between 5 & 10 random shuffles would multiply the number
Amir> of possible decks by 6 (10-5+1), or give you much more randomness.

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?).

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.

-- 
Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
<merlyn@stonehenge.com> <URL:http://www.stonehenge.com/merlyn/>
Perl/Unix/security consulting, Technical writing, Comedy, etc. etc.
See PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!

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