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

[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?

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

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.

TIA

 

[Tim Peters]

[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.

 

[Ben Cartwright]

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..

This change was necessary because the random module got a new default
generator in 2.3. The new generator uses the Mersenne Twister
algorithm. Pre 2.3, Wichmann-Hill was used. (For more details, search
for "jumpahead" in
http://www.python.org/download/releases/2.3/NEWS.txt)

Unlike WH, there isn't a way to directly compute the Nth number in the
sequence using MT. If you're curious as to why,
textbooks/journals/Google are your friends.

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?

You can always use the old WH generator. It's still available: 0.68591619673484816

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

Don't just suspect. Experiment, too.

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.

Python's random generator is implemented in C and is quite fast. In my
tests, your trudgeforward performs acceptably with n<~100000.

"import psyco" usually worth a try when improving execution speed, but
it won't help you here. All the real work is being done in C; the
overhead of the Python interpreter is neglible.

Hope that helps,
--Ben