[Python-Dev] a note in random.shuffle.__doc__ ...

[Nicko van Someren]

On 12 Jun 2006, at 02:19, Terry Jones wrote:

>>>>>> "Greg" == Greg Ewing <greg.ewing at canterbury.ac.nz> writes:
>
> Greg> Terry Jones wrote:
>>> Suppose you have a RNG with a cycle length of 5. There's nothing  
>>> to stop an
>>> algorithm from taking multiple already returned values and  
>>> combining them
>>> in some (deterministic) way to generate > 5 outcomes.
>
> Greg> No, it's not. As long as the RNG output is the only input to
> Greg> the algorithm, and the algorithm is deterministic, it is
> Greg> not possible get more than N different outcomes. It doesn't
> Greg> matter what the algorithm does with the input.
...
> The code below uses a RNG with period 5, is deterministic, and has one
> initial state. It produces 20 different outcomes.

I think that in any meaningful sense your code is producing just one  
outcome, since it has just one initial state.  It is completely  
deterministic and has no seed, so this is expected.

> It's just doing a simplistic version of what a lagged RNG generator  
> does,
> but the lagged part is in the "algorithm" not in the rng. That's  
> why I said
> if you included the state of the algorithm in what you meant by  
> "state" I'd
> be more inclined to agree.

This is a different issue.  You instantiate more than one PRNG.  If  
you have n PRGNs which each have a period p then you can get have the  
combination in p^n different starting states, which can be useful but  
only if you can find n*log2(p) bits of starting entropy to get the  
thing into a usefully random state.

	Nicko


> def rng():
...
>     history = [rng()]
...
>     for lag in range(1, 5):
...
>             new = rng()