random.jumpahead: How to jump ahead exactly N steps?

Tim Peters tim.peters at gmail.com
Thu Jun 22 00:39:14 CEST 2006


[Matthew Wilson]
> The random.jumpahead documentation says this:
>
>     Changed in version 2.3: Instead of jumping to a specific state, n steps
>     ahead, jumpahead(n) jumps to another state likely to be separated by
>     many steps..
>
> I really want a way to get to the Nth value in a random series started
> with a particular seed.  Is there any way to quickly do what jumpahead
> apparently used to do?

No known way, and it seems unlikely that any quick way will be found
in my lifetime ;-) for the Mersenne Twister.  In Pythons <= 2.2, the
underlying generator was the algebraically _very_ much simpler
original Wichman-Hill generator, and jumping ahead by exactly n steps
was just a matter of a few modular integer exponentiations.  That took
time proportional to log(n), so was extremely fast.

It was also much more _necessary_ using W-H, since W-H's period was
only around 10**13, while the Twister's period is around 10**6001:
even if you're going to use a billion random numbers per sequence, the
Twister's period has a way-way-beyond astronomical number of
non-overlapping subsequences of that length.  The chance of hitting an
overlap is correspondingly miniscule.

> I devised this function, but I suspect it runs really slowly:

Well, it takes exactly as much time as it takes to call random() n times.

> def trudgeforward(n):
>     '''Advance the random generator's state by n calls.'''
>     for _ in xrange(n): random.random()
>
> So any speed tips would be very appreciated.

What are you trying to achieve in the end?  Take it as a fact that
there is no known way to advance the Twister by n states faster than
what you've already found.



More information about the Python-list mailing list