>> I'm pretty sure he means that the first number is seen again as (say) #1001, and then again at #2001, and then again at #3001, and then again at #4001, and then again at #5001, at which point the claim that the period of the prng = 1000 looks pretty good.
Right, well the entire sequence inclusive. So for example:
(27)(68)(27)(36)(27)(31)(27)(24)(27)(17)
Even though the value 27 occurs regularly this would not be considered a periodic sequence. But now let's say we have this:
(22)(68)(13)(27)(21)(31)(12)(83)(36)(27)
Still fine, but now we can see that after generating the last number in the sequence that it is also present in the 4th position. So to test for periodicity, we "walk" the length of the sequence up to and including the last one shown, invoking the generator at every step and testing it against the number in that position. If we reach the end we assume that the sequence is periodic and return the length of the period. Otherwise, we append all of the numbers that were generated during the comparison onto the original sequence and continue the process. To make it more clear, this is the actual function:
Code:
/*
Returns either the period of the generator or zero if none
was found within the maximum number of iterations allowed
*/
template < typename Type, typename Generator >
size_t period_of_generator( Generator generator, size_t iterations )
{
vector< Type >
buffer,
saved;
for( ;; )
{
if( iterations-- == 0 )
return 0;
Type
value = generator( );
typename vector< Type >::const_iterator
begin = buffer.begin( ),
end = buffer.end( ),
found = find( begin, end, value );
if( found == end )
buffer.push_back( value );
else
{
saved.push_back( value );
while( ++found != end )
{
if( iterations-- == 0 )
return 0;
value = generator( );
saved.push_back( value );
if( value != *found )
break;
}
if( found == end )
return saved.size( );
buffer.insert( buffer.end( ), saved.begin( ), saved.end( ) );
saved.clear( );
}
}
return 0;
}
Of course I can see now that this isn't really a true test of periodicity, and it would probably be more useful if it had an option to make several passes and return "a degree of certainty". But even as is, when used on really good random number generators at several million iterations it is a reliable test of the function's *lack* of periodicity, anyway - which is helpful.