Message347055
If you want to be able to switch to something more efficient for large `n`, Knuth describes a simple O(log(n)) algorithm in TAOCP volume 4 (and attributes it to J. H. Ahrens). It's essentially a bisection search on the value, using the fact that we can use the beta distribution to generate order statistics. Here's a (too) simple Python implementation. It still needs thorough testing, and could be optimised in many ways - e.g., using sensible crossover point for n and not recursing all the way to n = 0.
def binomialvariate(n, p):
if n == 0:
return 0
a, b = (1 + n)//2, 1 + n//2
x = betavariate(a, b)
if x < p:
return a + binomialvariate(b - 1, (p - x)/(1 - x))
else:
return binomialvariate(a - 1, p/x)
>>> binomialvariate(10**10, 0.5)
4999944649 |
|
Date |
User |
Action |
Args |
2019-07-01 17:56:20 | mark.dickinson | set | recipients:
+ mark.dickinson, tim.peters, rhettinger |
2019-07-01 17:56:20 | mark.dickinson | set | messageid: <1562003780.81.0.556506493916.issue37439@roundup.psfhosted.org> |
2019-07-01 17:56:20 | mark.dickinson | link | issue37439 messages |
2019-07-01 17:56:20 | mark.dickinson | create | |
|