Re: [FWP] Shufflebug

[abigail@delanet.com]

On Tue, Jul 18, 2000 at 02:23:38PM -0700, Randal L. Schwartz wrote:
> >>>>> "abigail" == abigail  <abigail@delanet.com> writes:
> 
> >> You need to re-seed roughly
> >> every 32/6 calls to rand (right Abigail?).
> 
> abigail> No. You will have to reseed after *EVERY CALL*. Think about it. It'll
> abigail> be impossible for rand() to get the same outcome twice in a row (if i
> abigail> would, it would never get anything else). But for a truely random (bu
> abigail> finite precision) generator, getting the same outcome twice in a row
> abigail> has to be possible.
> 
> Uh, no, wait.  int(1 + rand 52) can return the same number twice.  in
> fact, it uses up only log(52)/log(2) = 5.7 bits each time.  Can't we
> show that for srand($_) for 0..2**32 that two calls to int(1 + rand
> 52) will cover every possibly combination nearly equally well?  And
> that three calls use up only 17 bits?  And 4 calls uses up 23 bits?
> So we could reseed every 4 calls to get 1..52 and still be "truly"
> random, with some bits to spare.  5 if we want to cut it close.
> 
> Or am I totally fricked up on the math here?

Yes.

There isn't anything like "bits to spare" when using rand. rand() returns
a bit pattern. That bit pattern is used to generate the next bit pattern.
And only that bit pattern is used, and nothing else. 

True, int (1 + rand 52) might return the same value repeatedly. But that's
just because it's doing a surjection - the mapping isn't a bijection.

The bit juggling you are showing above basically boils down to: rand()
returns a 32 bit pattern. We only need 6 bits to pick an integer from
1 .. 52, so just chop the 32 bit into 5 pieces. For linear congruential
pseudo-random generators, that is a really bad idea. I am sure you are
for instance familiar to the repeated bit pattern of the last bits of
rand().... I think Knuth has something to say about this as well.

You might as well say: Math::TruelyRandom generates 32 bits each time.
We chop that up in pieces of 6 bits. But I don't know whether that is
a good idea.



Abigail

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