1"""Random variable generators. 2 3 bytes 4 ----- 5 uniform bytes (values between 0 and 255) 6 7 integers 8 -------- 9 uniform within range 10 11 sequences 12 --------- 13 pick random element 14 pick random sample 15 pick weighted random sample 16 generate random permutation 17 18 distributions on the real line: 19 ------------------------------ 20 uniform 21 triangular 22 normal (Gaussian) 23 lognormal 24 negative exponential 25 gamma 26 beta 27 pareto 28 Weibull 29 30 distributions on the circle (angles 0 to 2pi) 31 --------------------------------------------- 32 circular uniform 33 von Mises 34 35General notes on the underlying Mersenne Twister core generator: 36 37* The period is 2**19937-1. 38* It is one of the most extensively tested generators in existence. 39* The random() method is implemented in C, executes in a single Python step, 40 and is, therefore, threadsafe. 41 42""" 43 44# Translated by Guido van Rossum from C source provided by 45# Adrian Baddeley. Adapted by Raymond Hettinger for use with 46# the Mersenne Twister and os.urandom() core generators. 47 48from warnings import warn as _warn 49from math import log as _log, exp as _exp, pi as _pi, e as _e, ceil as _ceil 50from math import sqrt as _sqrt, acos as _acos, cos as _cos, sin as _sin 51from math import tau as TWOPI, floor as _floor, isfinite as _isfinite 52from os import urandom as _urandom 53from _collections_abc import Set as _Set, Sequence as _Sequence 54from operator import index as _index 55from itertools import accumulate as _accumulate, repeat as _repeat 56from bisect import bisect as _bisect 57import os as _os 58import _random 59 60try: 61 # hashlib is pretty heavy to load, try lean internal module first 62 from _sha512 import sha512 as _sha512 63except ImportError: 64 # fallback to official implementation 65 from hashlib import sha512 as _sha512 66 67__all__ = [ 68 "Random", 69 "SystemRandom", 70 "betavariate", 71 "choice", 72 "choices", 73 "expovariate", 74 "gammavariate", 75 "gauss", 76 "getrandbits", 77 "getstate", 78 "lognormvariate", 79 "normalvariate", 80 "paretovariate", 81 "randbytes", 82 "randint", 83 "random", 84 "randrange", 85 "sample", 86 "seed", 87 "setstate", 88 "shuffle", 89 "triangular", 90 "uniform", 91 "vonmisesvariate", 92 "weibullvariate", 93] 94 95NV_MAGICCONST = 4 * _exp(-0.5) / _sqrt(2.0) 96LOG4 = _log(4.0) 97SG_MAGICCONST = 1.0 + _log(4.5) 98BPF = 53 # Number of bits in a float 99RECIP_BPF = 2 ** -BPF 100_ONE = 1 101 102 103class Random(_random.Random): 104 """Random number generator base class used by bound module functions. 105 106 Used to instantiate instances of Random to get generators that don't 107 share state. 108 109 Class Random can also be subclassed if you want to use a different basic 110 generator of your own devising: in that case, override the following 111 methods: random(), seed(), getstate(), and setstate(). 112 Optionally, implement a getrandbits() method so that randrange() 113 can cover arbitrarily large ranges. 114 115 """ 116 117 VERSION = 3 # used by getstate/setstate 118 119 def __init__(self, x=None): 120 """Initialize an instance. 121 122 Optional argument x controls seeding, as for Random.seed(). 123 """ 124 125 self.seed(x) 126 self.gauss_next = None 127 128 def seed(self, a=None, version=2): 129 """Initialize internal state from a seed. 130 131 The only supported seed types are None, int, float, 132 str, bytes, and bytearray. 133 134 None or no argument seeds from current time or from an operating 135 system specific randomness source if available. 136 137 If *a* is an int, all bits are used. 138 139 For version 2 (the default), all of the bits are used if *a* is a str, 140 bytes, or bytearray. For version 1 (provided for reproducing random 141 sequences from older versions of Python), the algorithm for str and 142 bytes generates a narrower range of seeds. 143 144 """ 145 146 if version == 1 and isinstance(a, (str, bytes)): 147 a = a.decode('latin-1') if isinstance(a, bytes) else a 148 x = ord(a[0]) << 7 if a else 0 149 for c in map(ord, a): 150 x = ((1000003 * x) ^ c) & 0xFFFFFFFFFFFFFFFF 151 x ^= len(a) 152 a = -2 if x == -1 else x 153 154 elif version == 2 and isinstance(a, (str, bytes, bytearray)): 155 if isinstance(a, str): 156 a = a.encode() 157 a = int.from_bytes(a + _sha512(a).digest()) 158 159 elif not isinstance(a, (type(None), int, float, str, bytes, bytearray)): 160 raise TypeError('The only supported seed types are: None,\n' 161 'int, float, str, bytes, and bytearray.') 162 163 super().seed(a) 164 self.gauss_next = None 165 166 def getstate(self): 167 """Return internal state; can be passed to setstate() later.""" 168 return self.VERSION, super().getstate(), self.gauss_next 169 170 def setstate(self, state): 171 """Restore internal state from object returned by getstate().""" 172 version = state[0] 173 if version == 3: 174 version, internalstate, self.gauss_next = state 175 super().setstate(internalstate) 176 elif version == 2: 177 version, internalstate, self.gauss_next = state 178 # In version 2, the state was saved as signed ints, which causes 179 # inconsistencies between 32/64-bit systems. The state is 180 # really unsigned 32-bit ints, so we convert negative ints from 181 # version 2 to positive longs for version 3. 182 try: 183 internalstate = tuple(x % (2 ** 32) for x in internalstate) 184 except ValueError as e: 185 raise TypeError from e 186 super().setstate(internalstate) 187 else: 188 raise ValueError("state with version %s passed to " 189 "Random.setstate() of version %s" % 190 (version, self.VERSION)) 191 192 193 ## ------------------------------------------------------- 194 ## ---- Methods below this point do not need to be overridden or extended 195 ## ---- when subclassing for the purpose of using a different core generator. 196 197 198 ## -------------------- pickle support ------------------- 199 200 # Issue 17489: Since __reduce__ was defined to fix #759889 this is no 201 # longer called; we leave it here because it has been here since random was 202 # rewritten back in 2001 and why risk breaking something. 203 def __getstate__(self): # for pickle 204 return self.getstate() 205 206 def __setstate__(self, state): # for pickle 207 self.setstate(state) 208 209 def __reduce__(self): 210 return self.__class__, (), self.getstate() 211 212 213 ## ---- internal support method for evenly distributed integers ---- 214 215 def __init_subclass__(cls, /, **kwargs): 216 """Control how subclasses generate random integers. 217 218 The algorithm a subclass can use depends on the random() and/or 219 getrandbits() implementation available to it and determines 220 whether it can generate random integers from arbitrarily large 221 ranges. 222 """ 223 224 for c in cls.__mro__: 225 if '_randbelow' in c.__dict__: 226 # just inherit it 227 break 228 if 'getrandbits' in c.__dict__: 229 cls._randbelow = cls._randbelow_with_getrandbits 230 break 231 if 'random' in c.__dict__: 232 cls._randbelow = cls._randbelow_without_getrandbits 233 break 234 235 def _randbelow_with_getrandbits(self, n): 236 "Return a random int in the range [0,n). Defined for n > 0." 237 238 getrandbits = self.getrandbits 239 k = n.bit_length() # don't use (n-1) here because n can be 1 240 r = getrandbits(k) # 0 <= r < 2**k 241 while r >= n: 242 r = getrandbits(k) 243 return r 244 245 def _randbelow_without_getrandbits(self, n, maxsize=1<<BPF): 246 """Return a random int in the range [0,n). Defined for n > 0. 247 248 The implementation does not use getrandbits, but only random. 249 """ 250 251 random = self.random 252 if n >= maxsize: 253 _warn("Underlying random() generator does not supply \n" 254 "enough bits to choose from a population range this large.\n" 255 "To remove the range limitation, add a getrandbits() method.") 256 return _floor(random() * n) 257 rem = maxsize % n 258 limit = (maxsize - rem) / maxsize # int(limit * maxsize) % n == 0 259 r = random() 260 while r >= limit: 261 r = random() 262 return _floor(r * maxsize) % n 263 264 _randbelow = _randbelow_with_getrandbits 265 266 267 ## -------------------------------------------------------- 268 ## ---- Methods below this point generate custom distributions 269 ## ---- based on the methods defined above. They do not 270 ## ---- directly touch the underlying generator and only 271 ## ---- access randomness through the methods: random(), 272 ## ---- getrandbits(), or _randbelow(). 273 274 275 ## -------------------- bytes methods --------------------- 276 277 def randbytes(self, n): 278 """Generate n random bytes.""" 279 return self.getrandbits(n * 8).to_bytes(n, 'little') 280 281 282 ## -------------------- integer methods ------------------- 283 284 def randrange(self, start, stop=None, step=_ONE): 285 """Choose a random item from range(stop) or range(start, stop[, step]). 286 287 Roughly equivalent to ``choice(range(start, stop, step))`` but 288 supports arbitrarily large ranges and is optimized for common cases. 289 290 """ 291 292 # This code is a bit messy to make it fast for the 293 # common case while still doing adequate error checking. 294 try: 295 istart = _index(start) 296 except TypeError: 297 istart = int(start) 298 if istart != start: 299 _warn('randrange() will raise TypeError in the future', 300 DeprecationWarning, 2) 301 raise ValueError("non-integer arg 1 for randrange()") 302 _warn('non-integer arguments to randrange() have been deprecated ' 303 'since Python 3.10 and will be removed in a subsequent ' 304 'version', 305 DeprecationWarning, 2) 306 if stop is None: 307 # We don't check for "step != 1" because it hasn't been 308 # type checked and converted to an integer yet. 309 if step is not _ONE: 310 raise TypeError('Missing a non-None stop argument') 311 if istart > 0: 312 return self._randbelow(istart) 313 raise ValueError("empty range for randrange()") 314 315 # stop argument supplied. 316 try: 317 istop = _index(stop) 318 except TypeError: 319 istop = int(stop) 320 if istop != stop: 321 _warn('randrange() will raise TypeError in the future', 322 DeprecationWarning, 2) 323 raise ValueError("non-integer stop for randrange()") 324 _warn('non-integer arguments to randrange() have been deprecated ' 325 'since Python 3.10 and will be removed in a subsequent ' 326 'version', 327 DeprecationWarning, 2) 328 width = istop - istart 329 try: 330 istep = _index(step) 331 except TypeError: 332 istep = int(step) 333 if istep != step: 334 _warn('randrange() will raise TypeError in the future', 335 DeprecationWarning, 2) 336 raise ValueError("non-integer step for randrange()") 337 _warn('non-integer arguments to randrange() have been deprecated ' 338 'since Python 3.10 and will be removed in a subsequent ' 339 'version', 340 DeprecationWarning, 2) 341 # Fast path. 342 if istep == 1: 343 if width > 0: 344 return istart + self._randbelow(width) 345 raise ValueError("empty range for randrange() (%d, %d, %d)" % (istart, istop, width)) 346 347 # Non-unit step argument supplied. 348 if istep > 0: 349 n = (width + istep - 1) // istep 350 elif istep < 0: 351 n = (width + istep + 1) // istep 352 else: 353 raise ValueError("zero step for randrange()") 354 if n <= 0: 355 raise ValueError("empty range for randrange()") 356 return istart + istep * self._randbelow(n) 357 358 def randint(self, a, b): 359 """Return random integer in range [a, b], including both end points. 360 """ 361 362 return self.randrange(a, b+1) 363 364 365 ## -------------------- sequence methods ------------------- 366 367 def choice(self, seq): 368 """Choose a random element from a non-empty sequence.""" 369 370 # As an accommodation for NumPy, we don't use "if not seq" 371 # because bool(numpy.array()) raises a ValueError. 372 if not len(seq): 373 raise IndexError('Cannot choose from an empty sequence') 374 return seq[self._randbelow(len(seq))] 375 376 def shuffle(self, x): 377 """Shuffle list x in place, and return None.""" 378 379 randbelow = self._randbelow 380 for i in reversed(range(1, len(x))): 381 # pick an element in x[:i+1] with which to exchange x[i] 382 j = randbelow(i + 1) 383 x[i], x[j] = x[j], x[i] 384 385 def sample(self, population, k, *, counts=None): 386 """Chooses k unique random elements from a population sequence. 387 388 Returns a new list containing elements from the population while 389 leaving the original population unchanged. The resulting list is 390 in selection order so that all sub-slices will also be valid random 391 samples. This allows raffle winners (the sample) to be partitioned 392 into grand prize and second place winners (the subslices). 393 394 Members of the population need not be hashable or unique. If the 395 population contains repeats, then each occurrence is a possible 396 selection in the sample. 397 398 Repeated elements can be specified one at a time or with the optional 399 counts parameter. For example: 400 401 sample(['red', 'blue'], counts=[4, 2], k=5) 402 403 is equivalent to: 404 405 sample(['red', 'red', 'red', 'red', 'blue', 'blue'], k=5) 406 407 To choose a sample from a range of integers, use range() for the 408 population argument. This is especially fast and space efficient 409 for sampling from a large population: 410 411 sample(range(10000000), 60) 412 413 """ 414 415 # Sampling without replacement entails tracking either potential 416 # selections (the pool) in a list or previous selections in a set. 417 418 # When the number of selections is small compared to the 419 # population, then tracking selections is efficient, requiring 420 # only a small set and an occasional reselection. For 421 # a larger number of selections, the pool tracking method is 422 # preferred since the list takes less space than the 423 # set and it doesn't suffer from frequent reselections. 424 425 # The number of calls to _randbelow() is kept at or near k, the 426 # theoretical minimum. This is important because running time 427 # is dominated by _randbelow() and because it extracts the 428 # least entropy from the underlying random number generators. 429 430 # Memory requirements are kept to the smaller of a k-length 431 # set or an n-length list. 432 433 # There are other sampling algorithms that do not require 434 # auxiliary memory, but they were rejected because they made 435 # too many calls to _randbelow(), making them slower and 436 # causing them to eat more entropy than necessary. 437 438 if not isinstance(population, _Sequence): 439 raise TypeError("Population must be a sequence. " 440 "For dicts or sets, use sorted(d).") 441 n = len(population) 442 if counts is not None: 443 cum_counts = list(_accumulate(counts)) 444 if len(cum_counts) != n: 445 raise ValueError('The number of counts does not match the population') 446 total = cum_counts.pop() 447 if not isinstance(total, int): 448 raise TypeError('Counts must be integers') 449 if total <= 0: 450 raise ValueError('Total of counts must be greater than zero') 451 selections = self.sample(range(total), k=k) 452 bisect = _bisect 453 return [population[bisect(cum_counts, s)] for s in selections] 454 randbelow = self._randbelow 455 if not 0 <= k <= n: 456 raise ValueError("Sample larger than population or is negative") 457 result = [None] * k 458 setsize = 21 # size of a small set minus size of an empty list 459 if k > 5: 460 setsize += 4 ** _ceil(_log(k * 3, 4)) # table size for big sets 461 if n <= setsize: 462 # An n-length list is smaller than a k-length set. 463 # Invariant: non-selected at pool[0 : n-i] 464 pool = list(population) 465 for i in range(k): 466 j = randbelow(n - i) 467 result[i] = pool[j] 468 pool[j] = pool[n - i - 1] # move non-selected item into vacancy 469 else: 470 selected = set() 471 selected_add = selected.add 472 for i in range(k): 473 j = randbelow(n) 474 while j in selected: 475 j = randbelow(n) 476 selected_add(j) 477 result[i] = population[j] 478 return result 479 480 def choices(self, population, weights=None, *, cum_weights=None, k=1): 481 """Return a k sized list of population elements chosen with replacement. 482 483 If the relative weights or cumulative weights are not specified, 484 the selections are made with equal probability. 485 486 """ 487 random = self.random 488 n = len(population) 489 if cum_weights is None: 490 if weights is None: 491 floor = _floor 492 n += 0.0 # convert to float for a small speed improvement 493 return [population[floor(random() * n)] for i in _repeat(None, k)] 494 try: 495 cum_weights = list(_accumulate(weights)) 496 except TypeError: 497 if not isinstance(weights, int): 498 raise 499 k = weights 500 raise TypeError( 501 f'The number of choices must be a keyword argument: {k=}' 502 ) from None 503 elif weights is not None: 504 raise TypeError('Cannot specify both weights and cumulative weights') 505 if len(cum_weights) != n: 506 raise ValueError('The number of weights does not match the population') 507 total = cum_weights[-1] + 0.0 # convert to float 508 if total <= 0.0: 509 raise ValueError('Total of weights must be greater than zero') 510 if not _isfinite(total): 511 raise ValueError('Total of weights must be finite') 512 bisect = _bisect 513 hi = n - 1 514 return [population[bisect(cum_weights, random() * total, 0, hi)] 515 for i in _repeat(None, k)] 516 517 518 ## -------------------- real-valued distributions ------------------- 519 520 def uniform(self, a, b): 521 "Get a random number in the range [a, b) or [a, b] depending on rounding." 522 return a + (b - a) * self.random() 523 524 def triangular(self, low=0.0, high=1.0, mode=None): 525 """Triangular distribution. 526 527 Continuous distribution bounded by given lower and upper limits, 528 and having a given mode value in-between. 529 530 http://en.wikipedia.org/wiki/Triangular_distribution 531 532 """ 533 u = self.random() 534 try: 535 c = 0.5 if mode is None else (mode - low) / (high - low) 536 except ZeroDivisionError: 537 return low 538 if u > c: 539 u = 1.0 - u 540 c = 1.0 - c 541 low, high = high, low 542 return low + (high - low) * _sqrt(u * c) 543 544 def normalvariate(self, mu=0.0, sigma=1.0): 545 """Normal distribution. 546 547 mu is the mean, and sigma is the standard deviation. 548 549 """ 550 # Uses Kinderman and Monahan method. Reference: Kinderman, 551 # A.J. and Monahan, J.F., "Computer generation of random 552 # variables using the ratio of uniform deviates", ACM Trans 553 # Math Software, 3, (1977), pp257-260. 554 555 random = self.random 556 while True: 557 u1 = random() 558 u2 = 1.0 - random() 559 z = NV_MAGICCONST * (u1 - 0.5) / u2 560 zz = z * z / 4.0 561 if zz <= -_log(u2): 562 break 563 return mu + z * sigma 564 565 def gauss(self, mu=0.0, sigma=1.0): 566 """Gaussian distribution. 567 568 mu is the mean, and sigma is the standard deviation. This is 569 slightly faster than the normalvariate() function. 570 571 Not thread-safe without a lock around calls. 572 573 """ 574 # When x and y are two variables from [0, 1), uniformly 575 # distributed, then 576 # 577 # cos(2*pi*x)*sqrt(-2*log(1-y)) 578 # sin(2*pi*x)*sqrt(-2*log(1-y)) 579 # 580 # are two *independent* variables with normal distribution 581 # (mu = 0, sigma = 1). 582 # (Lambert Meertens) 583 # (corrected version; bug discovered by Mike Miller, fixed by LM) 584 585 # Multithreading note: When two threads call this function 586 # simultaneously, it is possible that they will receive the 587 # same return value. The window is very small though. To 588 # avoid this, you have to use a lock around all calls. (I 589 # didn't want to slow this down in the serial case by using a 590 # lock here.) 591 592 random = self.random 593 z = self.gauss_next 594 self.gauss_next = None 595 if z is None: 596 x2pi = random() * TWOPI 597 g2rad = _sqrt(-2.0 * _log(1.0 - random())) 598 z = _cos(x2pi) * g2rad 599 self.gauss_next = _sin(x2pi) * g2rad 600 601 return mu + z * sigma 602 603 def lognormvariate(self, mu, sigma): 604 """Log normal distribution. 605 606 If you take the natural logarithm of this distribution, you'll get a 607 normal distribution with mean mu and standard deviation sigma. 608 mu can have any value, and sigma must be greater than zero. 609 610 """ 611 return _exp(self.normalvariate(mu, sigma)) 612 613 def expovariate(self, lambd): 614 """Exponential distribution. 615 616 lambd is 1.0 divided by the desired mean. It should be 617 nonzero. (The parameter would be called "lambda", but that is 618 a reserved word in Python.) Returned values range from 0 to 619 positive infinity if lambd is positive, and from negative 620 infinity to 0 if lambd is negative. 621 622 """ 623 # lambd: rate lambd = 1/mean 624 # ('lambda' is a Python reserved word) 625 626 # we use 1-random() instead of random() to preclude the 627 # possibility of taking the log of zero. 628 return -_log(1.0 - self.random()) / lambd 629 630 def vonmisesvariate(self, mu, kappa): 631 """Circular data distribution. 632 633 mu is the mean angle, expressed in radians between 0 and 2*pi, and 634 kappa is the concentration parameter, which must be greater than or 635 equal to zero. If kappa is equal to zero, this distribution reduces 636 to a uniform random angle over the range 0 to 2*pi. 637 638 """ 639 # Based upon an algorithm published in: Fisher, N.I., 640 # "Statistical Analysis of Circular Data", Cambridge 641 # University Press, 1993. 642 643 # Thanks to Magnus Kessler for a correction to the 644 # implementation of step 4. 645 646 random = self.random 647 if kappa <= 1e-6: 648 return TWOPI * random() 649 650 s = 0.5 / kappa 651 r = s + _sqrt(1.0 + s * s) 652 653 while True: 654 u1 = random() 655 z = _cos(_pi * u1) 656 657 d = z / (r + z) 658 u2 = random() 659 if u2 < 1.0 - d * d or u2 <= (1.0 - d) * _exp(d): 660 break 661 662 q = 1.0 / r 663 f = (q + z) / (1.0 + q * z) 664 u3 = random() 665 if u3 > 0.5: 666 theta = (mu + _acos(f)) % TWOPI 667 else: 668 theta = (mu - _acos(f)) % TWOPI 669 670 return theta 671 672 def gammavariate(self, alpha, beta): 673 """Gamma distribution. Not the gamma function! 674 675 Conditions on the parameters are alpha > 0 and beta > 0. 676 677 The probability distribution function is: 678 679 x ** (alpha - 1) * math.exp(-x / beta) 680 pdf(x) = -------------------------------------- 681 math.gamma(alpha) * beta ** alpha 682 683 """ 684 # alpha > 0, beta > 0, mean is alpha*beta, variance is alpha*beta**2 685 686 # Warning: a few older sources define the gamma distribution in terms 687 # of alpha > -1.0 688 if alpha <= 0.0 or beta <= 0.0: 689 raise ValueError('gammavariate: alpha and beta must be > 0.0') 690 691 random = self.random 692 if alpha > 1.0: 693 694 # Uses R.C.H. Cheng, "The generation of Gamma 695 # variables with non-integral shape parameters", 696 # Applied Statistics, (1977), 26, No. 1, p71-74 697 698 ainv = _sqrt(2.0 * alpha - 1.0) 699 bbb = alpha - LOG4 700 ccc = alpha + ainv 701 702 while True: 703 u1 = random() 704 if not 1e-7 < u1 < 0.9999999: 705 continue 706 u2 = 1.0 - random() 707 v = _log(u1 / (1.0 - u1)) / ainv 708 x = alpha * _exp(v) 709 z = u1 * u1 * u2 710 r = bbb + ccc * v - x 711 if r + SG_MAGICCONST - 4.5 * z >= 0.0 or r >= _log(z): 712 return x * beta 713 714 elif alpha == 1.0: 715 # expovariate(1/beta) 716 return -_log(1.0 - random()) * beta 717 718 else: 719 # alpha is between 0 and 1 (exclusive) 720 # Uses ALGORITHM GS of Statistical Computing - Kennedy & Gentle 721 while True: 722 u = random() 723 b = (_e + alpha) / _e 724 p = b * u 725 if p <= 1.0: 726 x = p ** (1.0 / alpha) 727 else: 728 x = -_log((b - p) / alpha) 729 u1 = random() 730 if p > 1.0: 731 if u1 <= x ** (alpha - 1.0): 732 break 733 elif u1 <= _exp(-x): 734 break 735 return x * beta 736 737 def betavariate(self, alpha, beta): 738 """Beta distribution. 739 740 Conditions on the parameters are alpha > 0 and beta > 0. 741 Returned values range between 0 and 1. 742 743 """ 744 ## See 745 ## http://mail.python.org/pipermail/python-bugs-list/2001-January/003752.html 746 ## for Ivan Frohne's insightful analysis of why the original implementation: 747 ## 748 ## def betavariate(self, alpha, beta): 749 ## # Discrete Event Simulation in C, pp 87-88. 750 ## 751 ## y = self.expovariate(alpha) 752 ## z = self.expovariate(1.0/beta) 753 ## return z/(y+z) 754 ## 755 ## was dead wrong, and how it probably got that way. 756 757 # This version due to Janne Sinkkonen, and matches all the std 758 # texts (e.g., Knuth Vol 2 Ed 3 pg 134 "the beta distribution"). 759 y = self.gammavariate(alpha, 1.0) 760 if y: 761 return y / (y + self.gammavariate(beta, 1.0)) 762 return 0.0 763 764 def paretovariate(self, alpha): 765 """Pareto distribution. alpha is the shape parameter.""" 766 # Jain, pg. 495 767 768 u = 1.0 - self.random() 769 return u ** (-1.0 / alpha) 770 771 def weibullvariate(self, alpha, beta): 772 """Weibull distribution. 773 774 alpha is the scale parameter and beta is the shape parameter. 775 776 """ 777 # Jain, pg. 499; bug fix courtesy Bill Arms 778 779 u = 1.0 - self.random() 780 return alpha * (-_log(u)) ** (1.0 / beta) 781 782 783## ------------------------------------------------------------------ 784## --------------- Operating System Random Source ------------------ 785 786 787class SystemRandom(Random): 788 """Alternate random number generator using sources provided 789 by the operating system (such as /dev/urandom on Unix or 790 CryptGenRandom on Windows). 791 792 Not available on all systems (see os.urandom() for details). 793 794 """ 795 796 def random(self): 797 """Get the next random number in the range 0.0 <= X < 1.0.""" 798 return (int.from_bytes(_urandom(7)) >> 3) * RECIP_BPF 799 800 def getrandbits(self, k): 801 """getrandbits(k) -> x. Generates an int with k random bits.""" 802 if k < 0: 803 raise ValueError('number of bits must be non-negative') 804 numbytes = (k + 7) // 8 # bits / 8 and rounded up 805 x = int.from_bytes(_urandom(numbytes)) 806 return x >> (numbytes * 8 - k) # trim excess bits 807 808 def randbytes(self, n): 809 """Generate n random bytes.""" 810 # os.urandom(n) fails with ValueError for n < 0 811 # and returns an empty bytes string for n == 0. 812 return _urandom(n) 813 814 def seed(self, *args, **kwds): 815 "Stub method. Not used for a system random number generator." 816 return None 817 818 def _notimplemented(self, *args, **kwds): 819 "Method should not be called for a system random number generator." 820 raise NotImplementedError('System entropy source does not have state.') 821 getstate = setstate = _notimplemented 822 823 824# ---------------------------------------------------------------------- 825# Create one instance, seeded from current time, and export its methods 826# as module-level functions. The functions share state across all uses 827# (both in the user's code and in the Python libraries), but that's fine 828# for most programs and is easier for the casual user than making them 829# instantiate their own Random() instance. 830 831_inst = Random() 832seed = _inst.seed 833random = _inst.random 834uniform = _inst.uniform 835triangular = _inst.triangular 836randint = _inst.randint 837choice = _inst.choice 838randrange = _inst.randrange 839sample = _inst.sample 840shuffle = _inst.shuffle 841choices = _inst.choices 842normalvariate = _inst.normalvariate 843lognormvariate = _inst.lognormvariate 844expovariate = _inst.expovariate 845vonmisesvariate = _inst.vonmisesvariate 846gammavariate = _inst.gammavariate 847gauss = _inst.gauss 848betavariate = _inst.betavariate 849paretovariate = _inst.paretovariate 850weibullvariate = _inst.weibullvariate 851getstate = _inst.getstate 852setstate = _inst.setstate 853getrandbits = _inst.getrandbits 854randbytes = _inst.randbytes 855 856 857## ------------------------------------------------------ 858## ----------------- test program ----------------------- 859 860def _test_generator(n, func, args): 861 from statistics import stdev, fmean as mean 862 from time import perf_counter 863 864 t0 = perf_counter() 865 data = [func(*args) for i in _repeat(None, n)] 866 t1 = perf_counter() 867 868 xbar = mean(data) 869 sigma = stdev(data, xbar) 870 low = min(data) 871 high = max(data) 872 873 print(f'{t1 - t0:.3f} sec, {n} times {func.__name__}') 874 print('avg %g, stddev %g, min %g, max %g\n' % (xbar, sigma, low, high)) 875 876 877def _test(N=2000): 878 _test_generator(N, random, ()) 879 _test_generator(N, normalvariate, (0.0, 1.0)) 880 _test_generator(N, lognormvariate, (0.0, 1.0)) 881 _test_generator(N, vonmisesvariate, (0.0, 1.0)) 882 _test_generator(N, gammavariate, (0.01, 1.0)) 883 _test_generator(N, gammavariate, (0.1, 1.0)) 884 _test_generator(N, gammavariate, (0.1, 2.0)) 885 _test_generator(N, gammavariate, (0.5, 1.0)) 886 _test_generator(N, gammavariate, (0.9, 1.0)) 887 _test_generator(N, gammavariate, (1.0, 1.0)) 888 _test_generator(N, gammavariate, (2.0, 1.0)) 889 _test_generator(N, gammavariate, (20.0, 1.0)) 890 _test_generator(N, gammavariate, (200.0, 1.0)) 891 _test_generator(N, gauss, (0.0, 1.0)) 892 _test_generator(N, betavariate, (3.0, 3.0)) 893 _test_generator(N, triangular, (0.0, 1.0, 1.0 / 3.0)) 894 895 896## ------------------------------------------------------ 897## ------------------ fork support --------------------- 898 899if hasattr(_os, "fork"): 900 _os.register_at_fork(after_in_child=_inst.seed) 901 902 903if __name__ == '__main__': 904 _test() 905