random.jumpahead: How to jump ahead exactly N steps?
tim.peters at gmail.com
Thu Jun 22 00:39:14 CEST 2006
> 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