[issue37439] Add random.binomialvariate()

[Mark Dickinson]

Mark Dickinson  added the comment:

Nope, that's the wrong paper. It looks as though this is the right one, but 
it's hidden behind a paywall: https://dl.acm.org/doi/abs/10.1145/42372.42381

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue37439] Add random.binomialvariate()

[Mark Dickinson]

Mark Dickinson  added the comment:

I think the NumPy implementation may be from here: 
https://core.ac.uk/download/pdf/11007254.pdf

(though I'm struggling to find a clear citation in the NumPy source)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue37439] Add random.binomialvariate()

[Gregory P. Smith]

Gregory P. Smith  added the comment:

A presumed optimal version of this is already available in numpy.

https://numpy.org/doc/stable/reference/random/generated/numpy.random.Generator.binomial.html

https://github.com/numpy/numpy/blob/2232a473f8713f532c8164c8cf616f7bd05f54a7/numpy/random/_generator.pyx#L2805

--
nosy: +gregory.p.smith
versions: +Python 3.11 -Python 3.9

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue37439] Add random.binomialvariate()

[Zachary Kneupper]

Zachary Kneupper  added the comment:

Is adding random.binomialvariate() still under consideration?

I would be willing to work on this addition to Lib/random.py, as well as the 
accompanying tests and docs.

Should I use the type of algorithm hinted at by Mark on 2019-07-01 17:56?

--
nosy: +zkneupper

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue37439] Add random.binomialvariate()

[Raymond Hettinger]

Raymond Hettinger  added the comment:

[Avi]
> Shall I update the PR? 

Yes, please.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue37439] Add random.binomialvariate()

[Mark Dickinson]

Mark Dickinson  added the comment:

> [...] and then making algorithmic improvements later.

Though thinking about it, there is *one* catch: for the random module, it's 
nice if reproducibility isn't broken more often than necessary in released 
versions, so it would be best to do any algorithmic tweaking *before* 3.9.0 is 
released. But that still gives us some time ...

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue37439] Add random.binomialvariate()

[Mark Dickinson]

Mark Dickinson  added the comment:

@avi That's Raymond's call, but IMO there's absolutely nothing wrong with 
getting a reference implementation (with tests, documentation, and all the 
usual trimmings) in first and then making algorithmic improvements later. 

Thanks for the PR!

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue37439] Add random.binomialvariate()

[Avinash Sajjanshetty]

Avinash Sajjanshetty  added the comment:

@Mark - Newb here and before I could see your reply, I sent a PR cos I thought 
simple implementation provided by Raymond Hettinger was good enough. Shall I 
update the PR? 

I will add the tests soon.

--
nosy: +avi

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue37439] Add random.binomialvariate()

[Avinash Sajjanshetty]

Change by Avinash Sajjanshetty :


--
keywords: +patch
pull_requests: +14343
stage:  -> patch review
pull_request: https://github.com/python/cpython/pull/14530

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue37439] Add random.binomialvariate()

[Mark Dickinson]

Mark Dickinson  added the comment:

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)
444649

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue37439] Add random.binomialvariate()

[Raymond Hettinger]

Change by Raymond Hettinger :


--
Removed message: https://bugs.python.org/msg346817

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue37439] Add random.binomialvariate()

[Raymond Hettinger]

Raymond Hettinger  added the comment:

Instead of a O(n) simulation, an O(1) equivalent should be used.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue37439] Add random.binomialvariate()

[Raymond Hettinger]

New submission from Raymond Hettinger :

This a small snippet of code I written dozens of times.  It would be nice to 
have this in the library along with the other distributions.

def binomialvariate(n, p):
''' Binomial distribution for the number of successes
in *n* Bernoulli trials each with a probability *p*
of success.

Returns an integer in the range:  0 <= X <= n
'''
return sum(random() < p for i in range(n))

--
components: Library (Lib)
messages: 346815
nosy: mark.dickinson, rhettinger, tim.peters
priority: low
severity: normal
status: open
title: Add random.binomialvariate()
type: enhancement
versions: Python 3.9

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com