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