Fix bugs introduced by rewrite (in particular, time-based initialization

got broken).  Also added new method .jumpahead(N).  This finally gives us
a semi-decent answer to how Python's RNGs can be used safely and efficiently
in multithreaded programs (although it requires the user to use the new
machinery!).

3 files changed, 67 insertions, 17 deletions

diff --git a/Doc/lib/librandom.tex b/Doc/lib/librandom.tex
index 4e4d615..9d303c2 100644
--- a/Doc/lib/librandom.tex
+++ b/Doc/lib/librandom.tex
@@ -33,14 +33,15 @@ Else, because no critical sections are implemented internally, calls
 from different threads may see the same return values.
 
 The functions supplied by this module are actually bound methods of a
-hidden instance of the \var{random.Random} class.  You can instantiate
-your own instances of \var{Random} to get generators that don't share state.
-This may be especially useful for multi-threaded programs, although there's
-no simple way to seed the distinct generators to ensure that the generated
-sequences won't overlap.  Class \var{Random} can also be subclassed if you
-want to use a different basic generator of your own devising:  in that
-case, override the \method{random()}, \method{seed()}, \method{getstate()}
-and \method{setstate()} methods.
+hidden instance of the \var{random.Random} class.  You can instantiate your
+own instances of \var{Random} to get generators that don't share state.
+This is especially useful for multi-threaded programs, creating a different
+instance of \var{Random} for each thread, and using the \method{jumpahead()}
+method to ensure that the generated sequences seen by each thread don't
+overlap.  Class \var{Random} can also be subclassed if you want to use a
+different basic generator of your own devising:  in that case, override the
+\method{random()}, \method{seed()}, \method{getstate()},
+\method{setstate()} and \method{jumpahead()} methods.
 
 
 Bookkeeping functions:
@@ -68,6 +69,16 @@ Bookkeeping functions:
   of the generate to what it was at the time \code{setstate()} was called.
  \end{funcdesc}
 
+\begin{funcdesc}{jumpahead}{n}
+  Change the internal state to what it would be if \code{random()} were
+  called n times, but do so quickly.  \var{n} is a non-negative integer.
+  This is most useful in multi-threaded programs, in conjuction with
+  multiple instances of the \var{Random} class:  \method{setstate()} or
+  \method{seed()} can be used to force all instances into the same
+  internal state, and then \method{jumpahead()} can be used to force the
+  instances' states as far apart as you like (up to the period of the
+  generator).
+ \end{funcdesc}
 
 Functions for integers:
 
diff --git a/Lib/random.py b/Lib/random.py
index a818f73..1b91886 100644
--- a/Lib/random.py
+++ b/Lib/random.py
@@ -72,8 +72,8 @@ class Random:
         self.gauss_next = None
 
     # Specific to Wichmann-Hill generator.  Subclasses wishing to use a
-    # different core generator should override seed(), random(),  getstate()
-    # and setstate().
+    # different core generator should override the seed(), random(),
+    # getstate(), setstate(), and jumpahead() methods.
 
     def __whseed(self, x=0, y=0, z=0):
         """Set the Wichmann-Hill seed from (x, y, z).
@@ -104,6 +104,7 @@ class Random:
 
         if a is None:
             self.__whseed()
+            return
         a = hash(a)
         a, x = divmod(a, 256)
         a, y = divmod(a, 256)
@@ -115,11 +116,10 @@ class Random:
 
     def getstate(self):
         """Return internal state; can be passed to setstate() later."""
-
         return self.VERSION, self._seed, self.gauss_next
 
     def __getstate__(self): # for pickle
-        self.getstate()
+        return self.getstate()
 
     def setstate(self, state):
         """Restore internal state from object returned by getstate()."""
@@ -134,6 +134,28 @@ class Random:
     def __setstate__(self, state):  # for pickle
         self.setstate(state)
 
+    def jumpahead(self, n):
+        """Act as if n calls to random() were made, but quickly.
+
+        n is an int, greater than or equal to 0.
+
+        Example use:  If you have 2 threads and know that each will
+        consume no more than a million random numbers, create two Random
+        objects r1 and r2, then do
+            r2.setstate(r1.getstate())
+            r2.jumpahead(1000000)
+        Then r1 and r2 will use guaranteed-disjoint segments of the full
+        period.
+        """
+
+        if not n >= 0:
+            raise ValueError("n must be >= 0")
+        x, y, z = self._seed
+        x = int(x * pow(171, n, 30269)) % 30269
+        y = int(y * pow(172, n, 30307)) % 30307
+        z = int(z * pow(170, n, 30323)) % 30323
+        self._seed = x, y, z
+
     def random(self):
         """Get the next random number in the range [0.0, 1.0)."""
 
@@ -471,6 +493,17 @@ def _test_generator(n, funccall):
     print 'avg %g, stddev %g, min %g, max %g' % \
               (avg, stddev, smallest, largest)
 
+    s = getstate()
+    N = 1019
+    jumpahead(N)
+    r1 = random()
+    setstate(s)
+    for i in range(N):  # now do it the slow way
+        random()
+    r2 = random()
+    if r1 != r2:
+        raise ValueError("jumpahead test failed " + `(N, r1, r2)`)
+
 def _test(N=200):
     print 'TWOPI         =', TWOPI
     print 'LOG4          =', LOG4
@@ -515,6 +548,7 @@ paretovariate = _inst.paretovariate
 weibullvariate = _inst.weibullvariate
 getstate = _inst.getstate
 setstate = _inst.setstate
+jumpahead = _inst.jumpahead
 
 if __name__ == '__main__':
     _test()
diff --git a/Misc/NEWS b/Misc/NEWS
index 058d55c..def0dd3 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -8,7 +8,12 @@ Standard library
 - random.py is now self-contained, and offers all the functionality of
   the now-deprecated whrandom.py.  See the docs for details.  random.py
   also supports new functions getstate() and setstate(), for saving
-  and restoring the internal state of all the generators.
+  and restoring the internal state of the generator; and jumpahead(n),
+  for quickly forcing the internal state to be the same as if n calls to
+  random() had been made.  The latter is particularly useful for multi-
+  threaded programs, creating one instance of the random.Random() class for
+  each thread, then using .jumpahead() to force each instance to use a
+  non-overlapping segment of the full period.
 
 
 What's New in Python 2.1 alpha 1?
@@ -107,12 +112,12 @@ Core language, builtins, and interpreter
   a complicated (but still thread-safe) method using fgets() is used by
   default.
 
-  You can force use of the fgets() method by #define'ing 
-  USE_FGETS_IN_GETLINE at build time (it may be faster than 
+  You can force use of the fgets() method by #define'ing
+  USE_FGETS_IN_GETLINE at build time (it may be faster than
   getc_unlocked()).
 
-  You can force fgets() not to be used by #define'ing 
-  DONT_USE_FGETS_IN_GETLINE (this is the first thing to try if std test 
+  You can force fgets() not to be used by #define'ing
+  DONT_USE_FGETS_IN_GETLINE (this is the first thing to try if std test
   test_bufio.py fails -- and let us know if it does!).
 
 - In addition, the fileinput module, while still slower than the other