Re^3: How likely is rand() to repeat? (srand)

[tye]

No. Perl's rand() is documented to be completely repeatable when given the same starting point (see srand). So the number of strings possible using just rand() is bound by roughly 2 ** (the number random bits) or, more correctly, the number of effectively different srand() values.

Update: And every implementation that I've seen uses a simple LCPRNG (Linear Congruential Psuedo-Random Number Generator). So each has a fixed number of possible values and it will simply cycle through those in the exact same order each time if you actually call it 2**$bits times. The number of effectively different seed values is called the "period".

Update: Oh, forgot to mention that some implementations intentionally use only a subset of the (upper) bits so the period can often be much higher than 2**$bits. For example, a period of 2**32 is quite common while many such implementations only use 16 bits of each result. And I'm not completely sure, in such a case, whether Perl Config reports that as 16 or 32 "random bits".

Note: Just FYI, the above two updates were posted within a few minutes of the original submission (and thus nearly 2 hours before the first reply).

[BrowserUk]

So each has a fixed number of possible values and it will simply cycle through those in the exact same order each time if you actually call it 2**$bits times. The number of effectively different seed values is called the "period".

Sorry tye, but you are very wrong on this, and I can prove it.

The "period" is the number of values you have to draw before the entire sequence of 2**n-bits values, repeat in the same sequence, in their entirety!

The Mersenne Twister MT19937, with 32-bit word length, has a period of 2¹⁹⁹³⁷ - 1. How could that be if your statement above was true?

Of course, that is not a LCPRNG.

But, the rand() provided by MSVC is a linear congruential PRNG. And it only produce 15-bits on entropy. Proof:

C:\test>perl -E"++$h{ int( rand 65536 ) } for 1 .. 1e6; say scalar key
+s %h; grep{ $_ & 1 } keys %h or say 'No odd numbers found'"
32768
No odd numbers found

And for the whole sequence to repeat, the first two values would have to repeat one after the other first. And according to you, that should happen within the first 32768 values produced.

It doesn't. (With srand(1)):

C:\test>randperiod -M=2
41 18467
i:1 n:412286284
First sequence of 2 values repeated itself after 412286284 calls to ra
+nd

That's 412 million values generated before the first pair are repeated in sequence.

Now let's try to match the first 3 values produced:

C:\test>randperiod -M=3
41 18467 6334
i:2 n:2147418117
First sequence of 3 values repeated itself after 2147418117 calls to r
+and

That's 2 billion values drawn before the first 3 values repeat in sequence.

The test code:

#! perl -slw
use strict;

sub rand32768{ int( rand 32768 ) }

$|++;
our $M //= 10;

srand( 1 );

my @first = map rand32768(), 1 .. $M;
print "@first";

my $n = $M;

OUTER: while( 1 ) {
    ++$n until rand32768 == $first[ 0 ];
    for my $i ( 1 .. $M - 1 ) {
        ++$n;
        printf "\ri:$i n:$n";
        redo OUTER unless rand32768() == $first[ $i ];
    }
    last;
}

print "\nFirst sequence of $M values repeated itself after $n calls to
+ rand";

I've tweaked the code to log how many value were drawn for each increasing length sequence. I'll leave it running over night.