source: python/vendor/Python-2.7.6/Lib/random.py

Last change on this file was 388, checked in by dmik, 11 years ago

python: Update vendor to 2.7.6.
  • Property svn:eol-style set to native
File size: 31.4 KB
Line 
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 triangular
17 normal (Gaussian)
18 lognormal
19 negative exponential
20 gamma
21 beta
22 pareto
23 Weibull
24
25 distributions on the circle (angles 0 to 2pi)
26 ---------------------------------------------
27 circular uniform
28 von Mises
29
30General notes on the underlying Mersenne Twister core generator:
31
32* The period is 2**19937-1.
33* It is one of the most extensively tested generators in existence.
34* Without a direct way to compute N steps forward, the semantics of
35 jumpahead(n) are weakened to simply jump to another distant state and rely
36 on the large period to avoid overlapping sequences.
37* The random() method is implemented in C, executes in a single Python step,
38 and is, therefore, threadsafe.
39
40"""
41
42from __future__ import division
43from warnings import warn as _warn
44from types import MethodType as _MethodType, BuiltinMethodType as _BuiltinMethodType
45from math import log as _log, exp as _exp, pi as _pi, e as _e, ceil as _ceil
46from math import sqrt as _sqrt, acos as _acos, cos as _cos, sin as _sin
47from os import urandom as _urandom
48from binascii import hexlify as _hexlify
49import hashlib as _hashlib
50
51__all__ = ["Random","seed","random","uniform","randint","choice","sample",
52 "randrange","shuffle","normalvariate","lognormvariate",
53 "expovariate","vonmisesvariate","gammavariate","triangular",
54 "gauss","betavariate","paretovariate","weibullvariate",
55 "getstate","setstate","jumpahead", "WichmannHill", "getrandbits",
56 "SystemRandom"]
57
58NV_MAGICCONST = 4 * _exp(-0.5)/_sqrt(2.0)
59TWOPI = 2.0*_pi
60LOG4 = _log(4.0)
61SG_MAGICCONST = 1.0 + _log(4.5)
62BPF = 53 # Number of bits in a float
63RECIP_BPF = 2**-BPF
64
65
66# Translated by Guido van Rossum from C source provided by
67# Adrian Baddeley. Adapted by Raymond Hettinger for use with
68# the Mersenne Twister and os.urandom() core generators.
69
70import _random
71
72class Random(_random.Random):
73 """Random number generator base class used by bound module functions.
74
75 Used to instantiate instances of Random to get generators that don't
76 share state. Especially useful for multi-threaded programs, creating
77 a different instance of Random for each thread, and using the jumpahead()
78 method to ensure that the generated sequences seen by each thread don't
79 overlap.
80
81 Class Random can also be subclassed if you want to use a different basic
82 generator of your own devising: in that case, override the following
83 methods: random(), seed(), getstate(), setstate() and jumpahead().
84 Optionally, implement a getrandbits() method so that randrange() can cover
85 arbitrarily large ranges.
86
87 """
88
89 VERSION = 3 # used by getstate/setstate
90
91 def __init__(self, x=None):
92 """Initialize an instance.
93
94 Optional argument x controls seeding, as for Random.seed().
95 """
96
97 self.seed(x)
98 self.gauss_next = None
99
100 def seed(self, a=None):
101 """Initialize internal state from hashable object.
102
103 None or no argument seeds from current time or from an operating
104 system specific randomness source if available.
105
106 If a is not None or an int or long, hash(a) is used instead.
107 """
108
109 if a is None:
110 try:
111 a = long(_hexlify(_urandom(16)), 16)
112 except NotImplementedError:
113 import time
114 a = long(time.time() * 256) # use fractional seconds
115
116 super(Random, self).seed(a)
117 self.gauss_next = None
118
119 def getstate(self):
120 """Return internal state; can be passed to setstate() later."""
121 return self.VERSION, super(Random, self).getstate(), self.gauss_next
122
123 def setstate(self, state):
124 """Restore internal state from object returned by getstate()."""
125 version = state[0]
126 if version == 3:
127 version, internalstate, self.gauss_next = state
128 super(Random, self).setstate(internalstate)
129 elif version == 2:
130 version, internalstate, self.gauss_next = state
131 # In version 2, the state was saved as signed ints, which causes
132 # inconsistencies between 32/64-bit systems. The state is
133 # really unsigned 32-bit ints, so we convert negative ints from
134 # version 2 to positive longs for version 3.
135 try:
136 internalstate = tuple( long(x) % (2**32) for x in internalstate )
137 except ValueError, e:
138 raise TypeError, e
139 super(Random, self).setstate(internalstate)
140 else:
141 raise ValueError("state with version %s passed to "
142 "Random.setstate() of version %s" %
143 (version, self.VERSION))
144
145 def jumpahead(self, n):
146 """Change the internal state to one that is likely far away
147 from the current state. This method will not be in Py3.x,
148 so it is better to simply reseed.
149 """
150 # The super.jumpahead() method uses shuffling to change state,
151 # so it needs a large and "interesting" n to work with. Here,
152 # we use hashing to create a large n for the shuffle.
153 s = repr(n) + repr(self.getstate())
154 n = int(_hashlib.new('sha512', s).hexdigest(), 16)
155 super(Random, self).jumpahead(n)
156
157## ---- Methods below this point do not need to be overridden when
158## ---- subclassing for the purpose of using a different core generator.
159
160## -------------------- pickle support -------------------
161
162 def __getstate__(self): # for pickle
163 return self.getstate()
164
165 def __setstate__(self, state): # for pickle
166 self.setstate(state)
167
168 def __reduce__(self):
169 return self.__class__, (), self.getstate()
170
171## -------------------- integer methods -------------------
172
173 def randrange(self, start, stop=None, step=1, _int=int, _maxwidth=1L<<BPF):
174 """Choose a random item from range(start, stop[, step]).
175
176 This fixes the problem with randint() which includes the
177 endpoint; in Python this is usually not what you want.
178
179 """
180
181 # This code is a bit messy to make it fast for the
182 # common case while still doing adequate error checking.
183 istart = _int(start)
184 if istart != start:
185 raise ValueError, "non-integer arg 1 for randrange()"
186 if stop is None:
187 if istart > 0:
188 if istart >= _maxwidth:
189 return self._randbelow(istart)
190 return _int(self.random() * istart)
191 raise ValueError, "empty range for randrange()"
192
193 # stop argument supplied.
194 istop = _int(stop)
195 if istop != stop:
196 raise ValueError, "non-integer stop for randrange()"
197 width = istop - istart
198 if step == 1 and width > 0:
199 # Note that
200 # int(istart + self.random()*width)
201 # instead would be incorrect. For example, consider istart
202 # = -2 and istop = 0. Then the guts would be in
203 # -2.0 to 0.0 exclusive on both ends (ignoring that random()
204 # might return 0.0), and because int() truncates toward 0, the
205 # final result would be -1 or 0 (instead of -2 or -1).
206 # istart + int(self.random()*width)
207 # would also be incorrect, for a subtler reason: the RHS
208 # can return a long, and then randrange() would also return
209 # a long, but we're supposed to return an int (for backward
210 # compatibility).
211
212 if width >= _maxwidth:
213 return _int(istart + self._randbelow(width))
214 return _int(istart + _int(self.random()*width))
215 if step == 1:
216 raise ValueError, "empty range for randrange() (%d,%d, %d)" % (istart, istop, width)
217
218 # Non-unit step argument supplied.
219 istep = _int(step)
220 if istep != step:
221 raise ValueError, "non-integer step for randrange()"
222 if istep > 0:
223 n = (width + istep - 1) // istep
224 elif istep < 0:
225 n = (width + istep + 1) // istep
226 else:
227 raise ValueError, "zero step for randrange()"
228
229 if n <= 0:
230 raise ValueError, "empty range for randrange()"
231
232 if n >= _maxwidth:
233 return istart + istep*self._randbelow(n)
234 return istart + istep*_int(self.random() * n)
235
236 def randint(self, a, b):
237 """Return random integer in range [a, b], including both end points.
238 """
239
240 return self.randrange(a, b+1)
241
242 def _randbelow(self, n, _log=_log, _int=int, _maxwidth=1L<<BPF,
243 _Method=_MethodType, _BuiltinMethod=_BuiltinMethodType):
244 """Return a random int in the range [0,n)
245
246 Handles the case where n has more bits than returned
247 by a single call to the underlying generator.
248 """
249
250 try:
251 getrandbits = self.getrandbits
252 except AttributeError:
253 pass
254 else:
255 # Only call self.getrandbits if the original random() builtin method
256 # has not been overridden or if a new getrandbits() was supplied.
257 # This assures that the two methods correspond.
258 if type(self.random) is _BuiltinMethod or type(getrandbits) is _Method:
259 k = _int(1.00001 + _log(n-1, 2.0)) # 2**k > n-1 > 2**(k-2)
260 r = getrandbits(k)
261 while r >= n:
262 r = getrandbits(k)
263 return r
264 if n >= _maxwidth:
265 _warn("Underlying random() generator does not supply \n"
266 "enough bits to choose from a population range this large")
267 return _int(self.random() * n)
268
269## -------------------- sequence methods -------------------
270
271 def choice(self, seq):
272 """Choose a random element from a non-empty sequence."""
273 return seq[int(self.random() * len(seq))] # raises IndexError if seq is empty
274
275 def shuffle(self, x, random=None):
276 """x, random=random.random -> shuffle list x in place; return None.
277
278 Optional arg random is a 0-argument function returning a random
279 float in [0.0, 1.0); by default, the standard random.random.
280
281 """
282
283 if random is None:
284 random = self.random
285 _int = int
286 for i in reversed(xrange(1, len(x))):
287 # pick an element in x[:i+1] with which to exchange x[i]
288 j = _int(random() * (i+1))
289 x[i], x[j] = x[j], x[i]
290
291 def sample(self, population, k):
292 """Chooses k unique random elements from a population sequence.
293
294 Returns a new list containing elements from the population while
295 leaving the original population unchanged. The resulting list is
296 in selection order so that all sub-slices will also be valid random
297 samples. This allows raffle winners (the sample) to be partitioned
298 into grand prize and second place winners (the subslices).
299
300 Members of the population need not be hashable or unique. If the
301 population contains repeats, then each occurrence is a possible
302 selection in the sample.
303
304 To choose a sample in a range of integers, use xrange as an argument.
305 This is especially fast and space efficient for sampling from a
306 large population: sample(xrange(10000000), 60)
307 """
308
309 # Sampling without replacement entails tracking either potential
310 # selections (the pool) in a list or previous selections in a set.
311
312 # When the number of selections is small compared to the
313 # population, then tracking selections is efficient, requiring
314 # only a small set and an occasional reselection. For
315 # a larger number of selections, the pool tracking method is
316 # preferred since the list takes less space than the
317 # set and it doesn't suffer from frequent reselections.
318
319 n = len(population)
320 if not 0 <= k <= n:
321 raise ValueError("sample larger than population")
322 random = self.random
323 _int = int
324 result = [None] * k
325 setsize = 21 # size of a small set minus size of an empty list
326 if k > 5:
327 setsize += 4 ** _ceil(_log(k * 3, 4)) # table size for big sets
328 if n <= setsize or hasattr(population, "keys"):
329 # An n-length list is smaller than a k-length set, or this is a
330 # mapping type so the other algorithm wouldn't work.
331 pool = list(population)
332 for i in xrange(k): # invariant: non-selected at [0,n-i)
333 j = _int(random() * (n-i))
334 result[i] = pool[j]
335 pool[j] = pool[n-i-1] # move non-selected item into vacancy
336 else:
337 try:
338 selected = set()
339 selected_add = selected.add
340 for i in xrange(k):
341 j = _int(random() * n)
342 while j in selected:
343 j = _int(random() * n)
344 selected_add(j)
345 result[i] = population[j]
346 except (TypeError, KeyError): # handle (at least) sets
347 if isinstance(population, list):
348 raise
349 return self.sample(tuple(population), k)
350 return result
351
352## -------------------- real-valued distributions -------------------
353
354## -------------------- uniform distribution -------------------
355
356 def uniform(self, a, b):
357 "Get a random number in the range [a, b) or [a, b] depending on rounding."
358 return a + (b-a) * self.random()
359
360## -------------------- triangular --------------------
361
362 def triangular(self, low=0.0, high=1.0, mode=None):
363 """Triangular distribution.
364
365 Continuous distribution bounded by given lower and upper limits,
366 and having a given mode value in-between.
367
368 http://en.wikipedia.org/wiki/Triangular_distribution
369
370 """
371 u = self.random()
372 c = 0.5 if mode is None else (mode - low) / (high - low)
373 if u > c:
374 u = 1.0 - u
375 c = 1.0 - c
376 low, high = high, low
377 return low + (high - low) * (u * c) ** 0.5
378
379## -------------------- normal distribution --------------------
380
381 def normalvariate(self, mu, sigma):
382 """Normal distribution.
383
384 mu is the mean, and sigma is the standard deviation.
385
386 """
387 # mu = mean, sigma = standard deviation
388
389 # Uses Kinderman and Monahan method. Reference: Kinderman,
390 # A.J. and Monahan, J.F., "Computer generation of random
391 # variables using the ratio of uniform deviates", ACM Trans
392 # Math Software, 3, (1977), pp257-260.
393
394 random = self.random
395 while 1:
396 u1 = random()
397 u2 = 1.0 - random()
398 z = NV_MAGICCONST*(u1-0.5)/u2
399 zz = z*z/4.0
400 if zz <= -_log(u2):
401 break
402 return mu + z*sigma
403
404## -------------------- lognormal distribution --------------------
405
406 def lognormvariate(self, mu, sigma):
407 """Log normal distribution.
408
409 If you take the natural logarithm of this distribution, you'll get a
410 normal distribution with mean mu and standard deviation sigma.
411 mu can have any value, and sigma must be greater than zero.
412
413 """
414 return _exp(self.normalvariate(mu, sigma))
415
416## -------------------- exponential distribution --------------------
417
418 def expovariate(self, lambd):
419 """Exponential distribution.
420
421 lambd is 1.0 divided by the desired mean. It should be
422 nonzero. (The parameter would be called "lambda", but that is
423 a reserved word in Python.) Returned values range from 0 to
424 positive infinity if lambd is positive, and from negative
425 infinity to 0 if lambd is negative.
426
427 """
428 # lambd: rate lambd = 1/mean
429 # ('lambda' is a Python reserved word)
430
431 # we use 1-random() instead of random() to preclude the
432 # possibility of taking the log of zero.
433 return -_log(1.0 - self.random())/lambd
434
435## -------------------- von Mises distribution --------------------
436
437 def vonmisesvariate(self, mu, kappa):
438 """Circular data distribution.
439
440 mu is the mean angle, expressed in radians between 0 and 2*pi, and
441 kappa is the concentration parameter, which must be greater than or
442 equal to zero. If kappa is equal to zero, this distribution reduces
443 to a uniform random angle over the range 0 to 2*pi.
444
445 """
446 # mu: mean angle (in radians between 0 and 2*pi)
447 # kappa: concentration parameter kappa (>= 0)
448 # if kappa = 0 generate uniform random angle
449
450 # Based upon an algorithm published in: Fisher, N.I.,
451 # "Statistical Analysis of Circular Data", Cambridge
452 # University Press, 1993.
453
454 # Thanks to Magnus Kessler for a correction to the
455 # implementation of step 4.
456
457 random = self.random
458 if kappa <= 1e-6:
459 return TWOPI * random()
460
461 s = 0.5 / kappa
462 r = s + _sqrt(1.0 + s * s)
463
464 while 1:
465 u1 = random()
466 z = _cos(_pi * u1)
467
468 d = z / (r + z)
469 u2 = random()
470 if u2 < 1.0 - d * d or u2 <= (1.0 - d) * _exp(d):
471 break
472
473 q = 1.0 / r
474 f = (q + z) / (1.0 + q * z)
475 u3 = random()
476 if u3 > 0.5:
477 theta = (mu + _acos(f)) % TWOPI
478 else:
479 theta = (mu - _acos(f)) % TWOPI
480
481 return theta
482
483## -------------------- gamma distribution --------------------
484
485 def gammavariate(self, alpha, beta):
486 """Gamma distribution. Not the gamma function!
487
488 Conditions on the parameters are alpha > 0 and beta > 0.
489
490 The probability distribution function is:
491
492 x ** (alpha - 1) * math.exp(-x / beta)
493 pdf(x) = --------------------------------------
494 math.gamma(alpha) * beta ** alpha
495
496 """
497
498 # alpha > 0, beta > 0, mean is alpha*beta, variance is alpha*beta**2
499
500 # Warning: a few older sources define the gamma distribution in terms
501 # of alpha > -1.0
502 if alpha <= 0.0 or beta <= 0.0:
503 raise ValueError, 'gammavariate: alpha and beta must be > 0.0'
504
505 random = self.random
506 if alpha > 1.0:
507
508 # Uses R.C.H. Cheng, "The generation of Gamma
509 # variables with non-integral shape parameters",
510 # Applied Statistics, (1977), 26, No. 1, p71-74
511
512 ainv = _sqrt(2.0 * alpha - 1.0)
513 bbb = alpha - LOG4
514 ccc = alpha + ainv
515
516 while 1:
517 u1 = random()
518 if not 1e-7 < u1 < .9999999:
519 continue
520 u2 = 1.0 - random()
521 v = _log(u1/(1.0-u1))/ainv
522 x = alpha*_exp(v)
523 z = u1*u1*u2
524 r = bbb+ccc*v-x
525 if r + SG_MAGICCONST - 4.5*z >= 0.0 or r >= _log(z):
526 return x * beta
527
528 elif alpha == 1.0:
529 # expovariate(1)
530 u = random()
531 while u <= 1e-7:
532 u = random()
533 return -_log(u) * beta
534
535 else: # alpha is between 0 and 1 (exclusive)
536
537 # Uses ALGORITHM GS of Statistical Computing - Kennedy & Gentle
538
539 while 1:
540 u = random()
541 b = (_e + alpha)/_e
542 p = b*u
543 if p <= 1.0:
544 x = p ** (1.0/alpha)
545 else:
546 x = -_log((b-p)/alpha)
547 u1 = random()
548 if p > 1.0:
549 if u1 <= x ** (alpha - 1.0):
550 break
551 elif u1 <= _exp(-x):
552 break
553 return x * beta
554
555## -------------------- Gauss (faster alternative) --------------------
556
557 def gauss(self, mu, sigma):
558 """Gaussian distribution.
559
560 mu is the mean, and sigma is the standard deviation. This is
561 slightly faster than the normalvariate() function.
562
563 Not thread-safe without a lock around calls.
564
565 """
566
567 # When x and y are two variables from [0, 1), uniformly
568 # distributed, then
569 #
570 # cos(2*pi*x)*sqrt(-2*log(1-y))
571 # sin(2*pi*x)*sqrt(-2*log(1-y))
572 #
573 # are two *independent* variables with normal distribution
574 # (mu = 0, sigma = 1).
575 # (Lambert Meertens)
576 # (corrected version; bug discovered by Mike Miller, fixed by LM)
577
578 # Multithreading note: When two threads call this function
579 # simultaneously, it is possible that they will receive the
580 # same return value. The window is very small though. To
581 # avoid this, you have to use a lock around all calls. (I
582 # didn't want to slow this down in the serial case by using a
583 # lock here.)
584
585 random = self.random
586 z = self.gauss_next
587 self.gauss_next = None
588 if z is None:
589 x2pi = random() * TWOPI
590 g2rad = _sqrt(-2.0 * _log(1.0 - random()))
591 z = _cos(x2pi) * g2rad
592 self.gauss_next = _sin(x2pi) * g2rad
593
594 return mu + z*sigma
595
596## -------------------- beta --------------------
597## See
598## http://mail.python.org/pipermail/python-bugs-list/2001-January/003752.html
599## for Ivan Frohne's insightful analysis of why the original implementation:
600##
601## def betavariate(self, alpha, beta):
602## # Discrete Event Simulation in C, pp 87-88.
603##
604## y = self.expovariate(alpha)
605## z = self.expovariate(1.0/beta)
606## return z/(y+z)
607##
608## was dead wrong, and how it probably got that way.
609
610 def betavariate(self, alpha, beta):
611 """Beta distribution.
612
613 Conditions on the parameters are alpha > 0 and beta > 0.
614 Returned values range between 0 and 1.
615
616 """
617
618 # This version due to Janne Sinkkonen, and matches all the std
619 # texts (e.g., Knuth Vol 2 Ed 3 pg 134 "the beta distribution").
620 y = self.gammavariate(alpha, 1.)
621 if y == 0:
622 return 0.0
623 else:
624 return y / (y + self.gammavariate(beta, 1.))
625
626## -------------------- Pareto --------------------
627
628 def paretovariate(self, alpha):
629 """Pareto distribution. alpha is the shape parameter."""
630 # Jain, pg. 495
631
632 u = 1.0 - self.random()
633 return 1.0 / pow(u, 1.0/alpha)
634
635## -------------------- Weibull --------------------
636
637 def weibullvariate(self, alpha, beta):
638 """Weibull distribution.
639
640 alpha is the scale parameter and beta is the shape parameter.
641
642 """
643 # Jain, pg. 499; bug fix courtesy Bill Arms
644
645 u = 1.0 - self.random()
646 return alpha * pow(-_log(u), 1.0/beta)
647
648## -------------------- Wichmann-Hill -------------------
649
650class WichmannHill(Random):
651
652 VERSION = 1 # used by getstate/setstate
653
654 def seed(self, a=None):
655 """Initialize internal state from hashable object.
656
657 None or no argument seeds from current time or from an operating
658 system specific randomness source if available.
659
660 If a is not None or an int or long, hash(a) is used instead.
661
662 If a is an int or long, a is used directly. Distinct values between
663 0 and 27814431486575L inclusive are guaranteed to yield distinct
664 internal states (this guarantee is specific to the default
665 Wichmann-Hill generator).
666 """
667
668 if a is None:
669 try:
670 a = long(_hexlify(_urandom(16)), 16)
671 except NotImplementedError:
672 import time
673 a = long(time.time() * 256) # use fractional seconds
674
675 if not isinstance(a, (int, long)):
676 a = hash(a)
677
678 a, x = divmod(a, 30268)
679 a, y = divmod(a, 30306)
680 a, z = divmod(a, 30322)
681 self._seed = int(x)+1, int(y)+1, int(z)+1
682
683 self.gauss_next = None
684
685 def random(self):
686 """Get the next random number in the range [0.0, 1.0)."""
687
688 # Wichman-Hill random number generator.
689 #
690 # Wichmann, B. A. & Hill, I. D. (1982)
691 # Algorithm AS 183:
692 # An efficient and portable pseudo-random number generator
693 # Applied Statistics 31 (1982) 188-190
694 #
695 # see also:
696 # Correction to Algorithm AS 183
697 # Applied Statistics 33 (1984) 123
698 #
699 # McLeod, A. I. (1985)
700 # A remark on Algorithm AS 183
701 # Applied Statistics 34 (1985),198-200
702
703 # This part is thread-unsafe:
704 # BEGIN CRITICAL SECTION
705 x, y, z = self._seed
706 x = (171 * x) % 30269
707 y = (172 * y) % 30307
708 z = (170 * z) % 30323
709 self._seed = x, y, z
710 # END CRITICAL SECTION
711
712 # Note: on a platform using IEEE-754 double arithmetic, this can
713 # never return 0.0 (asserted by Tim; proof too long for a comment).
714 return (x/30269.0 + y/30307.0 + z/30323.0) % 1.0
715
716 def getstate(self):
717 """Return internal state; can be passed to setstate() later."""
718 return self.VERSION, self._seed, self.gauss_next
719
720 def setstate(self, state):
721 """Restore internal state from object returned by getstate()."""
722 version = state[0]
723 if version == 1:
724 version, self._seed, self.gauss_next = state
725 else:
726 raise ValueError("state with version %s passed to "
727 "Random.setstate() of version %s" %
728 (version, self.VERSION))
729
730 def jumpahead(self, n):
731 """Act as if n calls to random() were made, but quickly.
732
733 n is an int, greater than or equal to 0.
734
735 Example use: If you have 2 threads and know that each will
736 consume no more than a million random numbers, create two Random
737 objects r1 and r2, then do
738 r2.setstate(r1.getstate())
739 r2.jumpahead(1000000)
740 Then r1 and r2 will use guaranteed-disjoint segments of the full
741 period.
742 """
743
744 if not n >= 0:
745 raise ValueError("n must be >= 0")
746 x, y, z = self._seed
747 x = int(x * pow(171, n, 30269)) % 30269
748 y = int(y * pow(172, n, 30307)) % 30307
749 z = int(z * pow(170, n, 30323)) % 30323
750 self._seed = x, y, z
751
752 def __whseed(self, x=0, y=0, z=0):
753 """Set the Wichmann-Hill seed from (x, y, z).
754
755 These must be integers in the range [0, 256).
756 """
757
758 if not type(x) == type(y) == type(z) == int:
759 raise TypeError('seeds must be integers')
760 if not (0 <= x < 256 and 0 <= y < 256 and 0 <= z < 256):
761 raise ValueError('seeds must be in range(0, 256)')
762 if 0 == x == y == z:
763 # Initialize from current time
764 import time
765 t = long(time.time() * 256)
766 t = int((t&0xffffff) ^ (t>>24))
767 t, x = divmod(t, 256)
768 t, y = divmod(t, 256)
769 t, z = divmod(t, 256)
770 # Zero is a poor seed, so substitute 1
771 self._seed = (x or 1, y or 1, z or 1)
772
773 self.gauss_next = None
774
775 def whseed(self, a=None):
776 """Seed from hashable object's hash code.
777
778 None or no argument seeds from current time. It is not guaranteed
779 that objects with distinct hash codes lead to distinct internal
780 states.
781
782 This is obsolete, provided for compatibility with the seed routine
783 used prior to Python 2.1. Use the .seed() method instead.
784 """
785
786 if a is None:
787 self.__whseed()
788 return
789 a = hash(a)
790 a, x = divmod(a, 256)
791 a, y = divmod(a, 256)
792 a, z = divmod(a, 256)
793 x = (x + a) % 256 or 1
794 y = (y + a) % 256 or 1
795 z = (z + a) % 256 or 1
796 self.__whseed(x, y, z)
797
798## --------------- Operating System Random Source ------------------
799
800class SystemRandom(Random):
801 """Alternate random number generator using sources provided
802 by the operating system (such as /dev/urandom on Unix or
803 CryptGenRandom on Windows).
804
805 Not available on all systems (see os.urandom() for details).
806 """
807
808 def random(self):
809 """Get the next random number in the range [0.0, 1.0)."""
810 return (long(_hexlify(_urandom(7)), 16) >> 3) * RECIP_BPF
811
812 def getrandbits(self, k):
813 """getrandbits(k) -> x. Generates a long int with k random bits."""
814 if k <= 0:
815 raise ValueError('number of bits must be greater than zero')
816 if k != int(k):
817 raise TypeError('number of bits should be an integer')
818 bytes = (k + 7) // 8 # bits / 8 and rounded up
819 x = long(_hexlify(_urandom(bytes)), 16)
820 return x >> (bytes * 8 - k) # trim excess bits
821
822 def _stub(self, *args, **kwds):
823 "Stub method. Not used for a system random number generator."
824 return None
825 seed = jumpahead = _stub
826
827 def _notimplemented(self, *args, **kwds):
828 "Method should not be called for a system random number generator."
829 raise NotImplementedError('System entropy source does not have state.')
830 getstate = setstate = _notimplemented
831
832## -------------------- test program --------------------
833
834def _test_generator(n, func, args):
835 import time
836 print n, 'times', func.__name__
837 total = 0.0
838 sqsum = 0.0
839 smallest = 1e10
840 largest = -1e10
841 t0 = time.time()
842 for i in range(n):
843 x = func(*args)
844 total += x
845 sqsum = sqsum + x*x
846 smallest = min(x, smallest)
847 largest = max(x, largest)
848 t1 = time.time()
849 print round(t1-t0, 3), 'sec,',
850 avg = total/n
851 stddev = _sqrt(sqsum/n - avg*avg)
852 print 'avg %g, stddev %g, min %g, max %g' % \
853 (avg, stddev, smallest, largest)
854
855
856def _test(N=2000):
857 _test_generator(N, random, ())
858 _test_generator(N, normalvariate, (0.0, 1.0))
859 _test_generator(N, lognormvariate, (0.0, 1.0))
860 _test_generator(N, vonmisesvariate, (0.0, 1.0))
861 _test_generator(N, gammavariate, (0.01, 1.0))
862 _test_generator(N, gammavariate, (0.1, 1.0))
863 _test_generator(N, gammavariate, (0.1, 2.0))
864 _test_generator(N, gammavariate, (0.5, 1.0))
865 _test_generator(N, gammavariate, (0.9, 1.0))
866 _test_generator(N, gammavariate, (1.0, 1.0))
867 _test_generator(N, gammavariate, (2.0, 1.0))
868 _test_generator(N, gammavariate, (20.0, 1.0))
869 _test_generator(N, gammavariate, (200.0, 1.0))
870 _test_generator(N, gauss, (0.0, 1.0))
871 _test_generator(N, betavariate, (3.0, 3.0))
872 _test_generator(N, triangular, (0.0, 1.0, 1.0/3.0))
873
874# Create one instance, seeded from current time, and export its methods
875# as module-level functions. The functions share state across all uses
876#(both in the user's code and in the Python libraries), but that's fine
877# for most programs and is easier for the casual user than making them
878# instantiate their own Random() instance.
879
880_inst = Random()
881seed = _inst.seed
882random = _inst.random
883uniform = _inst.uniform
884triangular = _inst.triangular
885randint = _inst.randint
886choice = _inst.choice
887randrange = _inst.randrange
888sample = _inst.sample
889shuffle = _inst.shuffle
890normalvariate = _inst.normalvariate
891lognormvariate = _inst.lognormvariate
892expovariate = _inst.expovariate
893vonmisesvariate = _inst.vonmisesvariate
894gammavariate = _inst.gammavariate
895gauss = _inst.gauss
896betavariate = _inst.betavariate
897paretovariate = _inst.paretovariate
898weibullvariate = _inst.weibullvariate
899getstate = _inst.getstate
900setstate = _inst.setstate
901jumpahead = _inst.jumpahead
902getrandbits = _inst.getrandbits
903
904if __name__ == '__main__':
905 _test()
Note: See TracBrowser for help on using the repository browser.