Lib/random.py

   1 """Random variable generators.
   2
   3     integers
   4     --------
   5            uniform within range
   6
   7     sequences
   8     ---------
   9            pick random element
  10            pick random sample
  11            generate random permutation
  12
  13     distributions on the real line:
  14     ------------------------------
  15            uniform
  16            normal (Gaussian)
  17            lognormal
  18            negative exponential
  19            gamma
  20            beta
  21            pareto
  22            Weibull
  23
  24     distributions on the circle (angles 0 to 2pi)
  25     ---------------------------------------------
  26            circular uniform
  27            von Mises
  28
  29 General notes on the underlying Mersenne Twister core generator:
  30
  31 * The period is 2**19937-1.
  32 * It is one of the most extensively tested generators in existence
  33 * Without a direct way to compute N steps forward, the
  34   semantics of jumpahead(n) are weakened to simply jump
  35   to another distant state and rely on the large period
  36   to avoid overlapping sequences.
  37 * The random() method is implemented in C, executes in
  38   a single Python step, and is, therefore, threadsafe.
  39
  40 """
  41
  42 from math import log as _log, exp as _exp, pi as _pi, e as _e
  43 from math import sqrt as _sqrt, acos as _acos, cos as _cos, sin as _sin
  44 from math import floor as _floor
  45
  46 __all__ = ["Random","seed","random","uniform","randint","choice","sample",
  47            "randrange","shuffle","normalvariate","lognormvariate",
  48            "cunifvariate","expovariate","vonmisesvariate","gammavariate",
  49            "stdgamma","gauss","betavariate","paretovariate","weibullvariate",
  50            "getstate","setstate","jumpahead"]
  51
  52 NV_MAGICCONST = 4 * _exp(-0.5)/_sqrt(2.0)
  53 TWOPI = 2.0*_pi
  54 LOG4 = _log(4.0)
  55 SG_MAGICCONST = 1.0 + _log(4.5)
  56
  57 # Translated by Guido van Rossum from C source provided by
  58 # Adrian Baddeley.  Adapted by Raymond Hettinger for use with
  59 # the Mersenne Twister core generator.
  60
  61 import _random
  62
  63 class Random(_random.Random):
  64     """Random number generator base class used by bound module functions.
  65
  66     Used to instantiate instances of Random to get generators that don't
  67     share state.  Especially useful for multi-threaded programs, creating
  68     a different instance of Random for each thread, and using the jumpahead()
  69     method to ensure that the generated sequences seen by each thread don't
  70     overlap.
  71
  72     Class Random can also be subclassed if you want to use a different basic
  73     generator of your own devising: in that case, override the following
  74     methods:  random(), seed(), getstate(), setstate() and jumpahead().
  75
  76     """
  77
  78     VERSION = 2     # used by getstate/setstate
  79
  80     def __init__(self, x=None):
  81         """Initialize an instance.
  82
  83         Optional argument x controls seeding, as for Random.seed().
  84         """
  85
  86         self.seed(x)
  87         self.gauss_next = None
  88
  89     def seed(self, a=None):
  90         """Initialize internal state from hashable object.
  91
  92         None or no argument seeds from current time.
  93
  94         If a is not None or an int or long, hash(a) is used instead.
  95         """
  96
  97         super(Random, self).seed(a)
  98         self.gauss_next = None
  99
 100     def getstate(self):
 101         """Return internal state; can be passed to setstate() later."""
 102         return self.VERSION, super(Random, self).getstate(), self.gauss_next
 103
 104     def setstate(self, state):
 105         """Restore internal state from object returned by getstate()."""
 106         version = state[0]
 107         if version == 2:
 108             version, internalstate, self.gauss_next = state
 109             super(Random, self).setstate(internalstate)
 110         else:
 111             raise ValueError("state with version %s passed to "
 112                              "Random.setstate() of version %s" %
 113                              (version, self.VERSION))
 114
 115 ## ---- Methods below this point do not need to be overridden when
 116 ## ---- subclassing for the purpose of using a different core generator.
 117
 118 ## -------------------- pickle support  -------------------
 119
 120     def __getstate__(self): # for pickle
 121         return self.getstate()
 122
 123     def __setstate__(self, state):  # for pickle
 124         self.setstate(state)
 125
 126 ## -------------------- integer methods  -------------------
 127
 128     def randrange(self, start, stop=None, step=1, int=int, default=None):
 129         """Choose a random item from range(start, stop[, step]).
 130
 131         This fixes the problem with randint() which includes the
 132         endpoint; in Python this is usually not what you want.
 133         Do not supply the 'int' and 'default' arguments.
 134         """
 135
 136         # This code is a bit messy to make it fast for the
 137         # common case while still doing adequate error checking.
 138         istart = int(start)
 139         if istart != start:
 140             raise ValueError, "non-integer arg 1 for randrange()"
 141         if stop is default:
 142             if istart > 0:
 143                 return int(self.random() * istart)
 144             raise ValueError, "empty range for randrange()"
 145
 146         # stop argument supplied.
 147         istop = int(stop)
 148         if istop != stop:
 149             raise ValueError, "non-integer stop for randrange()"
 150         if step == 1 and istart < istop:
 151             try:
 152                 return istart + int(self.random()*(istop - istart))
 153             except OverflowError:
 154                 # This can happen if istop-istart > sys.maxint + 1, and
 155                 # multiplying by random() doesn't reduce it to something
 156                 # <= sys.maxint.  We know that the overall result fits
 157                 # in an int, and can still do it correctly via math.floor().
 158                 # But that adds another function call, so for speed we
 159                 # avoided that whenever possible.
 160                 return int(istart + _floor(self.random()*(istop - istart)))
 161         if step == 1:
 162             raise ValueError, "empty range for randrange()"
 163
 164         # Non-unit step argument supplied.
 165         istep = int(step)
 166         if istep != step:
 167             raise ValueError, "non-integer step for randrange()"
 168         if istep > 0:
 169             n = (istop - istart + istep - 1) / istep
 170         elif istep < 0:
 171             n = (istop - istart + istep + 1) / istep
 172         else:
 173             raise ValueError, "zero step for randrange()"
 174
 175         if n <= 0:
 176             raise ValueError, "empty range for randrange()"
 177         return istart + istep*int(self.random() * n)
 178
 179     def randint(self, a, b):
 180         """Return random integer in range [a, b], including both end points.
 181         """
 182
 183         return self.randrange(a, b+1)
 184
 185 ## -------------------- sequence methods  -------------------
 186
 187     def choice(self, seq):
 188         """Choose a random element from a non-empty sequence."""
 189         return seq[int(self.random() * len(seq))]
 190
 191     def shuffle(self, x, random=None, int=int):
 192         """x, random=random.random -> shuffle list x in place; return None.
 193
 194         Optional arg random is a 0-argument function returning a random
 195         float in [0.0, 1.0); by default, the standard random.random.
 196
 197         Note that for even rather small len(x), the total number of
 198         permutations of x is larger than the period of most random number
 199         generators; this implies that "most" permutations of a long
 200         sequence can never be generated.
 201         """
 202
 203         if random is None:
 204             random = self.random
 205         for i in xrange(len(x)-1, 0, -1):
 206             # pick an element in x[:i+1] with which to exchange x[i]
 207             j = int(random() * (i+1))
 208             x[i], x[j] = x[j], x[i]
 209
 210     def sample(self, population, k, int=int):
 211         """Chooses k unique random elements from a population sequence.
 212
 213         Returns a new list containing elements from the population while
 214         leaving the original population unchanged.  The resulting list is
 215         in selection order so that all sub-slices will also be valid random
 216         samples.  This allows raffle winners (the sample) to be partitioned
 217         into grand prize and second place winners (the subslices).
 218
 219         Members of the population need not be hashable or unique.  If the
 220         population contains repeats, then each occurrence is a possible
 221         selection in the sample.
 222
 223         To choose a sample in a range of integers, use xrange as an argument.
 224         This is especially fast and space efficient for sampling from a
 225         large population:   sample(xrange(10000000), 60)
 226         """
 227
 228         # Sampling without replacement entails tracking either potential
 229         # selections (the pool) in a list or previous selections in a
 230         # dictionary.
 231
 232         # When the number of selections is small compared to the population,
 233         # then tracking selections is efficient, requiring only a small
 234         # dictionary and an occasional reselection.  For a larger number of
 235         # selections, the pool tracking method is preferred since the list takes
 236         # less space than the dictionary and it doesn't suffer from frequent
 237         # reselections.
 238
 239         n = len(population)
 240         if not 0 <= k <= n:
 241             raise ValueError, "sample larger than population"
 242         random = self.random
 243         result = [None] * k
 244         if n < 6 * k:     # if n len list takes less space than a k len dict
 245             pool = list(population)
 246             for i in xrange(k):         # invariant:  non-selected at [0,n-i)
 247                 j = int(random() * (n-i))
 248                 result[i] = pool[j]
 249                 pool[j] = pool[n-i-1]   # move non-selected item into vacancy
 250         else:
 251             selected = {}
 252             for i in xrange(k):
 253                 j = int(random() * n)
 254                 while j in selected:
 255                     j = int(random() * n)
 256                 result[i] = selected[j] = population[j]
 257         return result
 258
 259 ## -------------------- real-valued distributions  -------------------
 260
 261 ## -------------------- uniform distribution -------------------
 262
 263     def uniform(self, a, b):
 264         """Get a random number in the range [a, b)."""
 265         return a + (b-a) * self.random()
 266
 267 ## -------------------- normal distribution --------------------
 268
 269     def normalvariate(self, mu, sigma):
 270         """Normal distribution.
 271
 272         mu is the mean, and sigma is the standard deviation.
 273
 274         """
 275         # mu = mean, sigma = standard deviation
 276
 277         # Uses Kinderman and Monahan method. Reference: Kinderman,
 278         # A.J. and Monahan, J.F., "Computer generation of random
 279         # variables using the ratio of uniform deviates", ACM Trans
 280         # Math Software, 3, (1977), pp257-260.
 281
 282         random = self.random
 283         while True:
 284             u1 = random()
 285             u2 = 1.0 - random()
 286             z = NV_MAGICCONST*(u1-0.5)/u2
 287             zz = z*z/4.0
 288             if zz <= -_log(u2):
 289                 break
 290         return mu + z*sigma
 291
 292 ## -------------------- lognormal distribution --------------------
 293
 294     def lognormvariate(self, mu, sigma):
 295         """Log normal distribution.
 296
 297         If you take the natural logarithm of this distribution, you'll get a
 298         normal distribution with mean mu and standard deviation sigma.
 299         mu can have any value, and sigma must be greater than zero.
 300
 301         """
 302         return _exp(self.normalvariate(mu, sigma))
 303
 304 ## -------------------- circular uniform --------------------
 305
 306     def cunifvariate(self, mean, arc):
 307         """Circular uniform distribution.
 308
 309         mean is the mean angle, and arc is the range of the distribution,
 310         centered around the mean angle.  Both values must be expressed in
 311         radians.  Returned values range between mean - arc/2 and
 312         mean + arc/2 and are normalized to between 0 and pi.
 313
 314         Deprecated in version 2.3.  Use:
 315             (mean + arc * (Random.random() - 0.5)) % Math.pi
 316
 317         """
 318         # mean: mean angle (in radians between 0 and pi)
 319         # arc:  range of distribution (in radians between 0 and pi)
 320         import warnings
 321         warnings.warn("The cunifvariate function is deprecated; Use (mean "
 322                       "+ arc * (Random.random() - 0.5)) % Math.pi instead",
 323                       DeprecationWarning)
 324
 325         return (mean + arc * (self.random() - 0.5)) % _pi
 326
 327 ## -------------------- exponential distribution --------------------
 328
 329     def expovariate(self, lambd):
 330         """Exponential distribution.
 331
 332         lambd is 1.0 divided by the desired mean.  (The parameter would be
 333         called "lambda", but that is a reserved word in Python.)  Returned
 334         values range from 0 to positive infinity.
 335
 336         """
 337         # lambd: rate lambd = 1/mean
 338         # ('lambda' is a Python reserved word)
 339
 340         random = self.random
 341         u = random()
 342         while u <= 1e-7:
 343             u = random()
 344         return -_log(u)/lambd
 345
 346 ## -------------------- von Mises distribution --------------------
 347
 348     def vonmisesvariate(self, mu, kappa):
 349         """Circular data distribution.
 350
 351         mu is the mean angle, expressed in radians between 0 and 2*pi, and
 352         kappa is the concentration parameter, which must be greater than or
 353         equal to zero.  If kappa is equal to zero, this distribution reduces
 354         to a uniform random angle over the range 0 to 2*pi.
 355
 356         """
 357         # mu:    mean angle (in radians between 0 and 2*pi)
 358         # kappa: concentration parameter kappa (>= 0)
 359         # if kappa = 0 generate uniform random angle
 360
 361         # Based upon an algorithm published in: Fisher, N.I.,
 362         # "Statistical Analysis of Circular Data", Cambridge
 363         # University Press, 1993.
 364
 365         # Thanks to Magnus Kessler for a correction to the
 366         # implementation of step 4.
 367
 368         random = self.random
 369         if kappa <= 1e-6:
 370             return TWOPI * random()
 371
 372         a = 1.0 + _sqrt(1.0 + 4.0 * kappa * kappa)
 373         b = (a - _sqrt(2.0 * a))/(2.0 * kappa)
 374         r = (1.0 + b * b)/(2.0 * b)
 375
 376         while True:
 377             u1 = random()
 378
 379             z = _cos(_pi * u1)
 380             f = (1.0 + r * z)/(r + z)
 381             c = kappa * (r - f)
 382
 383             u2 = random()
 384
 385             if not (u2 >= c * (2.0 - c) and u2 > c * _exp(1.0 - c)):
 386                 break
 387
 388         u3 = random()
 389         if u3 > 0.5:
 390             theta = (mu % TWOPI) + _acos(f)
 391         else:
 392             theta = (mu % TWOPI) - _acos(f)
 393
 394         return theta
 395
 396 ## -------------------- gamma distribution --------------------
 397
 398     def gammavariate(self, alpha, beta):
 399         """Gamma distribution.  Not the gamma function!
 400
 401         Conditions on the parameters are alpha > 0 and beta > 0.
 402
 403         """
 404
 405         # alpha > 0, beta > 0, mean is alpha*beta, variance is alpha*beta**2
 406
 407         # Warning: a few older sources define the gamma distribution in terms
 408         # of alpha > -1.0
 409         if alpha <= 0.0 or beta <= 0.0:
 410             raise ValueError, 'gammavariate: alpha and beta must be > 0.0'
 411
 412         random = self.random
 413         if alpha > 1.0:
 414
 415             # Uses R.C.H. Cheng, "The generation of Gamma
 416             # variables with non-integral shape parameters",
 417             # Applied Statistics, (1977), 26, No. 1, p71-74
 418
 419             ainv = _sqrt(2.0 * alpha - 1.0)
 420             bbb = alpha - LOG4
 421             ccc = alpha + ainv
 422
 423             while True:
 424                 u1 = random()
 425                 if not 1e-7 < u1 < .9999999:
 426                     continue
 427                 u2 = 1.0 - random()
 428                 v = _log(u1/(1.0-u1))/ainv
 429                 x = alpha*_exp(v)
 430                 z = u1*u1*u2
 431                 r = bbb+ccc*v-x
 432                 if r + SG_MAGICCONST - 4.5*z >= 0.0 or r >= _log(z):
 433                     return x * beta
 434
 435         elif alpha == 1.0:
 436             # expovariate(1)
 437             u = random()
 438             while u <= 1e-7:
 439                 u = random()
 440             return -_log(u) * beta
 441
 442         else:   # alpha is between 0 and 1 (exclusive)
 443
 444             # Uses ALGORITHM GS of Statistical Computing - Kennedy & Gentle
 445
 446             while True:
 447                 u = random()
 448                 b = (_e + alpha)/_e
 449                 p = b*u
 450                 if p <= 1.0:
 451                     x = pow(p, 1.0/alpha)
 452                 else:
 453                     # p > 1
 454                     x = -_log((b-p)/alpha)
 455                 u1 = random()
 456                 if not (((p <= 1.0) and (u1 > _exp(-x))) or
 457                           ((p > 1)  and  (u1 > pow(x, alpha - 1.0)))):
 458                     break
 459             return x * beta
 460
 461
 462     def stdgamma(self, alpha, ainv, bbb, ccc):
 463         # This method was (and shall remain) undocumented.
 464         # This method is deprecated
 465         # for the following reasons:
 466         # 1. Returns same as .gammavariate(alpha, 1.0)
 467         # 2. Requires caller to provide 3 extra arguments
 468         #    that are functions of alpha anyway
 469         # 3. Can't be used for alpha < 0.5
 470
 471         # ainv = sqrt(2 * alpha - 1)
 472         # bbb = alpha - log(4)
 473         # ccc = alpha + ainv
 474         import warnings
 475         warnings.warn("The stdgamma function is deprecated; "
 476                       "use gammavariate() instead",
 477                       DeprecationWarning)
 478         return self.gammavariate(alpha, 1.0)
 479
 480
 481
 482 ## -------------------- Gauss (faster alternative) --------------------
 483
 484     def gauss(self, mu, sigma):
 485         """Gaussian distribution.
 486
 487         mu is the mean, and sigma is the standard deviation.  This is
 488         slightly faster than the normalvariate() function.
 489
 490         Not thread-safe without a lock around calls.
 491
 492         """
 493
 494         # When x and y are two variables from [0, 1), uniformly
 495         # distributed, then
 496         #
 497         #    cos(2*pi*x)*sqrt(-2*log(1-y))
 498         #    sin(2*pi*x)*sqrt(-2*log(1-y))
 499         #
 500         # are two *independent* variables with normal distribution
 501         # (mu = 0, sigma = 1).
 502         # (Lambert Meertens)
 503         # (corrected version; bug discovered by Mike Miller, fixed by LM)
 504
 505         # Multithreading note: When two threads call this function
 506         # simultaneously, it is possible that they will receive the
 507         # same return value.  The window is very small though.  To
 508         # avoid this, you have to use a lock around all calls.  (I
 509         # didn't want to slow this down in the serial case by using a
 510         # lock here.)
 511
 512         random = self.random
 513         z = self.gauss_next
 514         self.gauss_next = None
 515         if z is None:
 516             x2pi = random() * TWOPI
 517             g2rad = _sqrt(-2.0 * _log(1.0 - random()))
 518             z = _cos(x2pi) * g2rad
 519             self.gauss_next = _sin(x2pi) * g2rad
 520
 521         return mu + z*sigma
 522
 523 ## -------------------- beta --------------------
 524 ## See
 525 ## http://sourceforge.net/bugs/?func=detailbug&bug_id=130030&group_id=5470
 526 ## for Ivan Frohne's insightful analysis of why the original implementation:
 527 ##
 528 ##    def betavariate(self, alpha, beta):
 529 ##        # Discrete Event Simulation in C, pp 87-88.
 530 ##
 531 ##        y = self.expovariate(alpha)
 532 ##        z = self.expovariate(1.0/beta)
 533 ##        return z/(y+z)
 534 ##
 535 ## was dead wrong, and how it probably got that way.
 536
 537     def betavariate(self, alpha, beta):
 538         """Beta distribution.
 539
 540         Conditions on the parameters are alpha > -1 and beta} > -1.
 541         Returned values range between 0 and 1.
 542
 543         """
 544
 545         # This version due to Janne Sinkkonen, and matches all the std
 546         # texts (e.g., Knuth Vol 2 Ed 3 pg 134 "the beta distribution").
 547         y = self.gammavariate(alpha, 1.)
 548         if y == 0:
 549             return 0.0
 550         else:
 551             return y / (y + self.gammavariate(beta, 1.))
 552
 553 ## -------------------- Pareto --------------------
 554
 555     def paretovariate(self, alpha):
 556         """Pareto distribution.  alpha is the shape parameter."""
 557         # Jain, pg. 495
 558
 559         u = 1.0 - self.random()
 560         return 1.0 / pow(u, 1.0/alpha)
 561
 562 ## -------------------- Weibull --------------------
 563
 564     def weibullvariate(self, alpha, beta):
 565         """Weibull distribution.
 566
 567         alpha is the scale parameter and beta is the shape parameter.
 568
 569         """
 570         # Jain, pg. 499; bug fix courtesy Bill Arms
 571
 572         u = 1.0 - self.random()
 573         return alpha * pow(-_log(u), 1.0/beta)
 574
 575 ## -------------------- Wichmann-Hill -------------------
 576
 577 class WichmannHill(Random):
 578
 579     VERSION = 1     # used by getstate/setstate
 580
 581     def seed(self, a=None):
 582         """Initialize internal state from hashable object.
 583
 584         None or no argument seeds from current time.
 585
 586         If a is not None or an int or long, hash(a) is used instead.
 587
 588         If a is an int or long, a is used directly.  Distinct values between
 589         0 and 27814431486575L inclusive are guaranteed to yield distinct
 590         internal states (this guarantee is specific to the default
 591         Wichmann-Hill generator).
 592         """
 593
 594         if a is None:
 595             # Initialize from current time
 596             import time
 597             a = long(time.time() * 256)
 598
 599         if not isinstance(a, (int, long)):
 600             a = hash(a)
 601
 602         a, x = divmod(a, 30268)
 603         a, y = divmod(a, 30306)
 604         a, z = divmod(a, 30322)
 605         self._seed = int(x)+1, int(y)+1, int(z)+1
 606
 607         self.gauss_next = None
 608
 609     def random(self):
 610         """Get the next random number in the range [0.0, 1.0)."""
 611
 612         # Wichman-Hill random number generator.
 613         #
 614         # Wichmann, B. A. & Hill, I. D. (1982)
 615         # Algorithm AS 183:
 616         # An efficient and portable pseudo-random number generator
 617         # Applied Statistics 31 (1982) 188-190
 618         #
 619         # see also:
 620         #        Correction to Algorithm AS 183
 621         #        Applied Statistics 33 (1984) 123
 622         #
 623         #        McLeod, A. I. (1985)
 624         #        A remark on Algorithm AS 183
 625         #        Applied Statistics 34 (1985),198-200
 626
 627         # This part is thread-unsafe:
 628         # BEGIN CRITICAL SECTION
 629         x, y, z = self._seed
 630         x = (171 * x) % 30269
 631         y = (172 * y) % 30307
 632         z = (170 * z) % 30323
 633         self._seed = x, y, z
 634         # END CRITICAL SECTION
 635
 636         # Note:  on a platform using IEEE-754 double arithmetic, this can
 637         # never return 0.0 (asserted by Tim; proof too long for a comment).
 638         return (x/30269.0 + y/30307.0 + z/30323.0) % 1.0
 639
 640     def getstate(self):
 641         """Return internal state; can be passed to setstate() later."""
 642         return self.VERSION, self._seed, self.gauss_next
 643
 644     def setstate(self, state):
 645         """Restore internal state from object returned by getstate()."""
 646         version = state[0]
 647         if version == 1:
 648             version, self._seed, self.gauss_next = state
 649         else:
 650             raise ValueError("state with version %s passed to "
 651                              "Random.setstate() of version %s" %
 652                              (version, self.VERSION))
 653
 654     def jumpahead(self, n):
 655         """Act as if n calls to random() were made, but quickly.
 656
 657         n is an int, greater than or equal to 0.
 658
 659         Example use:  If you have 2 threads and know that each will
 660         consume no more than a million random numbers, create two Random
 661         objects r1 and r2, then do
 662             r2.setstate(r1.getstate())
 663             r2.jumpahead(1000000)
 664         Then r1 and r2 will use guaranteed-disjoint segments of the full
 665         period.
 666         """
 667
 668         if not n >= 0:
 669             raise ValueError("n must be >= 0")
 670         x, y, z = self._seed
 671         x = int(x * pow(171, n, 30269)) % 30269
 672         y = int(y * pow(172, n, 30307)) % 30307
 673         z = int(z * pow(170, n, 30323)) % 30323
 674         self._seed = x, y, z
 675
 676     def __whseed(self, x=0, y=0, z=0):
 677         """Set the Wichmann-Hill seed from (x, y, z).
 678
 679         These must be integers in the range [0, 256).
 680         """
 681
 682         if not type(x) == type(y) == type(z) == int:
 683             raise TypeError('seeds must be integers')
 684         if not (0 <= x < 256 and 0 <= y < 256 and 0 <= z < 256):
 685             raise ValueError('seeds must be in range(0, 256)')
 686         if 0 == x == y == z:
 687             # Initialize from current time
 688             import time
 689             t = long(time.time() * 256)
 690             t = int((t&0xffffff) ^ (t>>24))
 691             t, x = divmod(t, 256)
 692             t, y = divmod(t, 256)
 693             t, z = divmod(t, 256)
 694         # Zero is a poor seed, so substitute 1
 695         self._seed = (x or 1, y or 1, z or 1)
 696
 697         self.gauss_next = None
 698
 699     def whseed(self, a=None):
 700         """Seed from hashable object's hash code.
 701
 702         None or no argument seeds from current time.  It is not guaranteed
 703         that objects with distinct hash codes lead to distinct internal
 704         states.
 705
 706         This is obsolete, provided for compatibility with the seed routine
 707         used prior to Python 2.1.  Use the .seed() method instead.
 708         """
 709
 710         if a is None:
 711             self.__whseed()
 712             return
 713         a = hash(a)
 714         a, x = divmod(a, 256)
 715         a, y = divmod(a, 256)
 716         a, z = divmod(a, 256)
 717         x = (x + a) % 256 or 1
 718         y = (y + a) % 256 or 1
 719         z = (z + a) % 256 or 1
 720         self.__whseed(x, y, z)
 721
 722 ## -------------------- test program --------------------
 723
 724 def _test_generator(n, funccall):
 725     import time
 726     print n, 'times', funccall
 727     code = compile(funccall, funccall, 'eval')
 728     sum = 0.0
 729     sqsum = 0.0
 730     smallest = 1e10
 731     largest = -1e10
 732     t0 = time.time()
 733     for i in range(n):
 734         x = eval(code)
 735         sum = sum + x
 736         sqsum = sqsum + x*x
 737         smallest = min(x, smallest)
 738         largest = max(x, largest)
 739     t1 = time.time()
 740     print round(t1-t0, 3), 'sec,',
 741     avg = sum/n
 742     stddev = _sqrt(sqsum/n - avg*avg)
 743     print 'avg %g, stddev %g, min %g, max %g' % \
 744               (avg, stddev, smallest, largest)
 745
 746
 747 def _test(N=2000):
 748     _test_generator(N, 'random()')
 749     _test_generator(N, 'normalvariate(0.0, 1.0)')
 750     _test_generator(N, 'lognormvariate(0.0, 1.0)')
 751     _test_generator(N, 'cunifvariate(0.0, 1.0)')
 752     _test_generator(N, 'vonmisesvariate(0.0, 1.0)')
 753     _test_generator(N, 'gammavariate(0.01, 1.0)')
 754     _test_generator(N, 'gammavariate(0.1, 1.0)')
 755     _test_generator(N, 'gammavariate(0.1, 2.0)')
 756     _test_generator(N, 'gammavariate(0.5, 1.0)')
 757     _test_generator(N, 'gammavariate(0.9, 1.0)')
 758     _test_generator(N, 'gammavariate(1.0, 1.0)')
 759     _test_generator(N, 'gammavariate(2.0, 1.0)')
 760     _test_generator(N, 'gammavariate(20.0, 1.0)')
 761     _test_generator(N, 'gammavariate(200.0, 1.0)')
 762     _test_generator(N, 'gauss(0.0, 1.0)')
 763     _test_generator(N, 'betavariate(3.0, 3.0)')
 764
 765 # Create one instance, seeded from current time, and export its methods
 766 # as module-level functions.  The functions share state across all uses
 767 #(both in the user's code and in the Python libraries), but that's fine
 768 # for most programs and is easier for the casual user than making them
 769 # instantiate their own Random() instance.
 770
 771 _inst = Random()
 772 seed = _inst.seed
 773 random = _inst.random
 774 uniform = _inst.uniform
 775 randint = _inst.randint
 776 choice = _inst.choice
 777 randrange = _inst.randrange
 778 sample = _inst.sample
 779 shuffle = _inst.shuffle
 780 normalvariate = _inst.normalvariate
 781 lognormvariate = _inst.lognormvariate
 782 cunifvariate = _inst.cunifvariate
 783 expovariate = _inst.expovariate
 784 vonmisesvariate = _inst.vonmisesvariate
 785 gammavariate = _inst.gammavariate
 786 stdgamma = _inst.stdgamma
 787 gauss = _inst.gauss
 788 betavariate = _inst.betavariate
 789 paretovariate = _inst.paretovariate
 790 weibullvariate = _inst.weibullvariate
 791 getstate = _inst.getstate
 792 setstate = _inst.setstate
 793 jumpahead = _inst.jumpahead
 794
 795 if __name__ == '__main__':
 796     _test()