[issue35431] Add a function for computing binomial coefficients to the math module

Serhiy Storchaka added the comment: New changeset 914d6b79735e5eabaf4e4d77e3f2ad4eae0beb9a by Serhiy Storchaka in branch '3.8': [3.8] bpo-35431: Test math.comb() and math.perm() for OverflowError only on CPython. (GH-14146) (#14226)

[issue35431] Add a function for computing binomial coefficients to the math module

Change by Serhiy Storchaka : -- pull_requests: +14060 pull_request: https://github.com/python/cpython/pull/14226 ___ Python tracker ___

[issue35431] Add a function for computing binomial coefficients to the math module

Serhiy Storchaka added the comment: New changeset 1b8a46d59734a77cd1f5ffcf3bdfcaafd58a87e7 by Serhiy Storchaka in branch 'master': bpo-35431: Test math.comb() and math.perm() for OverflowError only on CPython. (GH-14146)

[issue35431] Add a function for computing binomial coefficients to the math module

Change by Serhiy Storchaka : -- pull_requests: +13987 pull_request: https://github.com/python/cpython/pull/14146 ___ Python tracker ___

[issue35431] Add a function for computing binomial coefficients to the math module

Change by miss-islington : -- pull_requests: +13972 pull_request: https://github.com/python/cpython/pull/14125 ___ Python tracker ___

[issue35431] Add a function for computing binomial coefficients to the math module

Change by Mark Dickinson : -- pull_requests: +13746 pull_request: https://github.com/python/cpython/pull/13870 ___ Python tracker ___

[issue35431] Add a function for computing binomial coefficients to the math module

Change by Raymond Hettinger : -- resolution: -> fixed stage: patch review -> resolved status: open -> closed ___ Python tracker ___

[issue35431] Add a function for computing binomial coefficients to the math module

Change by Raymond Hettinger : -- pull_requests: +13687 pull_request: https://github.com/python/cpython/pull/13801 ___ Python tracker ___

[issue35431] Add a function for computing binomial coefficients to the math module

Raymond Hettinger added the comment: New changeset 963eb0f4738456455b9bef7eb531b46805415208 by Raymond Hettinger in branch 'master': bpo-35431: Drop the k <= n requirement (GH-13798) https://github.com/python/cpython/commit/963eb0f4738456455b9bef7eb531b46805415208 --

[issue35431] Add a function for computing binomial coefficients to the math module

Change by Raymond Hettinger : -- pull_requests: +13683 pull_request: https://github.com/python/cpython/pull/13798 ___ Python tracker ___

[issue35431] Add a function for computing binomial coefficients to the math module

Mark Dickinson added the comment: Fine by me. The same change should be applied to `math.perm`. -- ___ Python tracker ___ ___

[issue35431] Add a function for computing binomial coefficients to the math module

Raymond Hettinger added the comment: > If it were me, I'd drop the k <= n requirement +1 from me. -- versions: +Python 3.8 -Python 3.6 ___ Python tracker ___

[issue35431] Add a function for computing binomial coefficients to the math module

Tim Peters added the comment: Python needs a benevolent dictator ;-) I'd be happy for Mark, Raymond, or me to play that role here. If it were me, I'd drop the k <= n requirement: both arguments must be non-negative integers. Because a combinatorial (not factorial-, and certainly not

[issue35431] Add a function for computing binomial coefficients to the math module

Raymond Hettinger added the comment: I don't have a preference one way or the other (both ways have plausible arguments, error checking vs utility beyond simple combinatorics, and both ways have ample precedents). That said, if we're going to ultimately relax the constraints, it would be

[issue35431] Add a function for computing binomial coefficients to the math module

Mark Dickinson added the comment: Given that (a) we're right up against feature freeze, and (b) the discussions about API already happened in plenty of good time some months ago, leading to agreement on the initial API, I think we should avoid any last-minute changes and stick with what we

[issue35431] Add a function for computing binomial coefficients to the math module

Steven D'Aprano added the comment: For what its worth, there are concrete, practical applications for binomial coefficients with negative arguments. They are used in fractional calculus https://nrich.maths.org/1365 which in turn has applications in physics, chemistry and other sciences:

[issue35431] Add a function for computing binomial coefficients to the math module

Tim Peters added the comment: I'm not fatally opposed to relaxing k <= n. David makes some good points about it, and - as Raymond already noted - "0" is consistent with the behavior of itertools.combinations(). The docs would need to change, though, because the factorial "definition" would

[issue35431] Add a function for computing binomial coefficients to the math module

David Radcliffe added the comment: I understand that pure mathematics is not the primary use case. But I would expect that math.comb() would be used to implement mathematical formulas. As a simple example, the number of edges in a complete graph on n vertices is binomial(n, 2), and this should

[issue35431] Add a function for computing binomial coefficients to the math module

Tim Peters added the comment: I'm going to repeat part of an earlier comment :-) """ Please resist pointless feature creep. The original report was about comb(n, k) for integer n and k with 0 <= k <= n and that's all. Everyone who commented appeared to agree they'd find that useful. """

[issue35431] Add a function for computing binomial coefficients to the math module

Raymond Hettinger added the comment: Here are a few other data points. There is no consensus but either returning 0 or erroring out seem reasonable. MS Excel's COMBIN: If number < 0, number_chosen < 0, or number < number_chosen, COMBIN returns the #NUM! error value. Scipy.misc.comb: If k

[issue35431] Add a function for computing binomial coefficients to the math module

Tim Peters added the comment: I'm not convinced, although I agree relaxing k <= n is less damaging than relaxing k >= 0. Python isn't aimed at mathematicians (although some 3rd-party packages certainly are, and they're free to define things however they like). We have to trade off

[issue35431] Add a function for computing binomial coefficients to the math module

Mark Dickinson added the comment: > @David Ratcliffe Radcliffe! Apologies for the misspelling. It's still early in this timezone and I haven't had any coffee yet. -- ___ Python tracker

[issue35431] Add a function for computing binomial coefficients to the math module

Mark Dickinson added the comment: @David Ratcliffe > the sum of the first n positive integers is binomial(n+1, 2), and the formula > should still work if n is zero. I agree that's a convincing use-case. Can you think of any practical uses for allowing negative `k`? I can't. --

[issue35431] Add a function for computing binomial coefficients to the math module

David Radcliffe added the comment: I think that binomial(n, k) should return 0 when k > n or k < 0. This is a practical consideration. I'm concerned about evaluating sums involving binomial coefficients. Mathematicians are often rather loose about specifying the upper and lower bounds of

[issue35431] Add a function for computing binomial coefficients to the math module

Change by Raymond Hettinger : -- pull_requests: +13617 pull_request: https://github.com/python/cpython/pull/13734 ___ Python tracker ___

[issue35431] Add a function for computing binomial coefficients to the math module

Tim Peters added the comment: Strongly prefer requiring 0 <= k <= n at first. This is a programming language: it will be applied to real problems, not to abstract proofs where some slop can be helpful in reducing the number of cases that need to be considered. The Twitter fellow is

[issue35431] Add a function for computing binomial coefficients to the math module

Mark Dickinson added the comment: I'm particularly sceptical about real-world use-cases for k < 0. Maybe we should consider removing just the k > n requirement. -- ___ Python tracker

[issue35431] Add a function for computing binomial coefficients to the math module

Raymond Hettinger added the comment: > I'd say leave it as-is for 3.8, see what the reaction is, > and maybe relax constraints in 3.9 if that seems appropriate. I concur. That said, the referenced tweet was a reaction :-) FWIW, itertools.combinations(seq, r) returns 0 values when r >

[issue35431] Add a function for computing binomial coefficients to the math module

Mark Dickinson added the comment: > What are your thoughts? Sigh. I don't object to extending to `k < 0` and `k > n`, but once we've made that extension it's impossible to undo if we decide we'd rather have had the error checking. I'd really like to see some convincing use-cases. Quotes

[issue35431] Add a function for computing binomial coefficients to the math module

Pablo Galindo Salgado added the comment: Just a heads up from issue37125: The leak is was fixed by PR13725. -- ___ Python tracker ___

[issue35431] Add a function for computing binomial coefficients to the math module

Raymond Hettinger added the comment: One other idea: it may be worth putting in an alias for "binomial" to improve findability and readability in contexts where a person really does what binomial coefficients and is not otherwise thinking about counting contexts. --

[issue35431] Add a function for computing binomial coefficients to the math module

Raymond Hettinger added the comment: Mark, please see: https://twitter.com/daveinstpaul/status/1134919179361034240 What are your thoughts? -- ___ Python tracker ___

[issue35431] Add a function for computing binomial coefficients to the math module

Mark Dickinson added the comment: I'd expect any math module function accepting integers to be sufficiently duck-typed to accept integer-like things (i.e., objects that implement `__index__`), in just the same way that the regular math module functions (sin, log, atan, sqrt, ...) accept

[issue35431] Add a function for computing binomial coefficients to the math module

Serhiy Storchaka added the comment: NumPy integer types are not subclasses of int. -- ___ Python tracker ___ ___ Python-bugs-list

[issue35431] Add a function for computing binomial coefficients to the math module

Raymond Hettinger added the comment: Why do we want __index__ support? This seems like an unnecessary extension without relevant use cases. -- ___ Python tracker ___

[issue35431] Add a function for computing binomial coefficients to the math module

Change by Serhiy Storchaka : -- pull_requests: +13614 pull_request: https://github.com/python/cpython/pull/13731 ___ Python tracker ___

[issue35431] Add a function for computing binomial coefficients to the math module

Serhiy Storchaka added the comment: New changeset 2b843ac0ae745026ce39514573c5d075137bef65 by Serhiy Storchaka in branch 'master': bpo-35431: Refactor math.comb() implementation. (GH-13725) https://github.com/python/cpython/commit/2b843ac0ae745026ce39514573c5d075137bef65 --

[issue35431] Add a function for computing binomial coefficients to the math module

Pablo Galindo Salgado added the comment: math.comb is leaking, I opened https://bugs.python.org/issue37125 to track it. -- nosy: +pablogsal ___ Python tracker ___

[issue35431] Add a function for computing binomial coefficients to the math module

Serhiy Storchaka added the comment: PR 13725 is a technical fix/optimization/cleanup. Later we can apply algorithmic optimization. -- ___ Python tracker ___

[issue35431] Add a function for computing binomial coefficients to the math module

Change by Serhiy Storchaka : -- pull_requests: +13609 pull_request: https://github.com/python/cpython/pull/13725 ___ Python tracker ___

[issue35431] Add a function for computing binomial coefficients to the math module

Yash Aggarwal added the comment: Thanks @rhettinger for cleaning up the code and closing the pr. I didn't get what you meant by long, and sorry for not being much active as well. I am stuck with a pretty time consuming internship. -- versions: +Python 3.6 -Python 3.8

[issue35431] Add a function for computing binomial coefficients to the math module

Mark Dickinson added the comment: Thanks, Raymond. I'm planning to do a post-merge review and test this weekend. -- ___ Python tracker ___

[issue35431] Add a function for computing binomial coefficients to the math module

Raymond Hettinger added the comment: Leaving this open for a while in case there is more work that needs to be done or any further comments to be resolved. -- assignee: -> rhettinger ___ Python tracker

[issue35431] Add a function for computing binomial coefficients to the math module

Raymond Hettinger added the comment: New changeset 4a686504eb2bbf69adf78077458508a7ba131667 by Raymond Hettinger (Yash Aggarwal) in branch 'master': bpo-35431: Implemented math.comb (GH-11414) https://github.com/python/cpython/commit/4a686504eb2bbf69adf78077458508a7ba131667 --

[issue35431] Add a function for computing binomial coefficients to the math module

Yash Aggarwal added the comment: @mark.dickinson both pr's are more or less same. Keller was offline for some time so I made the new issue. They were merged later. Only difference is in unittests. I'd say it's up to you to decide which one to keep. --

[issue35431] Add a function for computing binomial coefficients to the math module

Mark Dickinson added the comment: @kellerfuchs @FR4NKESTI3N We seem to have two open PRs for this feature, both with some review comments. Which is the one true PR? Can we close the other one? -- ___ Python tracker

[issue35431] Add a function for computing binomial coefficients to the math module

Yash Aggarwal added the comment: @mark.dickinson Ok, then I will work on comb for now then. -- ___ Python tracker ___ ___

[issue35431] Add a function for computing binomial coefficients to the math module

Mark Dickinson added the comment: > Can I get a consensus on weather math.perm() is needed? It's not, for the purposes of this issue. I think `math.perm` should be the subject of a separate issue and discussion, and a separate PR. That way it doesn't block completion of this issue.

[issue35431] Add a function for computing binomial coefficients to the math module

Yash Aggarwal added the comment: Can I get a consensus on weather math.perm() is needed? -- ___ Python tracker ___ ___

[issue35431] Add a function for computing binomial coefficients to the math module

kellerfuchs added the comment: > Given that people clarified they prefer comb(), and that people conspicuously > didn't comment on it being entirely-opaque to people who do not elready know > what it is, I guess there is indeed consensus. commit afb3d36e82b8d690a410fa9dca8029a8fad42984

[issue35431] Add a function for computing binomial coefficients to the math module

kellerfuchs added the comment: @Steven > > This involved a few changes, which seem to reflect the consensus here: > > - raise ValueError if k>n ; > > - rename the function to math.combinations. > [...] > > As far as I can tell from the discussions here, Steven and you stated a > > preference

[issue35431] Add a function for computing binomial coefficients to the math module

Change by Jakub Wilk : -- nosy: +jwilk ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue35431] Add a function for computing binomial coefficients to the math module

Tim Peters added the comment: > As far as I can tell from the discussions here, Steven > and you stated a preference for the shortened names, and > that's it. Plus Mark, plus me - all backed "comb()" specifically. > I find it hard to imagine anyone needing combinations without > also needing

[issue35431] Add a function for computing binomial coefficients to the math module

Yash Aggarwal added the comment: Agreed, comb sounds much better than combination. And using the name binomial would make it sound like something that would puke out whole binomial series rather than a single coefficient(maybe leave it for that in case is it decided to be useful in the

[issue35431] Add a function for computing binomial coefficients to the math module

Raymond Hettinger added the comment: > But given the precedent set by itertools and math.factorial, > perhaps you are right and we ought to stick to the longer name I disagree. Let's stick with comb() which is what SciPy uses. It is tedious to write out combinations in a formula what

[issue35431] Add a function for computing binomial coefficients to the math module

Steven D'Aprano added the comment: > This involved a few changes, which seem to reflect the consensus here: > - raise ValueError if k>n ; > - rename the function to math.combinations. I see at least four people (myself, Raymond, Mark and Tim) giving comb as first choice, and I didn't see

[issue35431] Add a function for computing binomial coefficients to the math module

Steven D'Aprano added the comment: Sorry for the late reply, I missed Tim's comment when it first came through. > Please resist pointless feature creep. The original report was about > comb(n, k) for integer n and k with 0 <= k <= n and that's all. > Everyone who commented appeared to

[issue35431] Add a function for computing binomial coefficients to the math module

Josh Rosenberg added the comment: Steven: I'm assuming Brett rearranged the title to put emphasis on the new function and to place it earlier in the title. Especially important if you're reading e-mails with the old subject on an e-mail client with limited subject preview lengths, you end

[issue35431] Add a function for computing binomial coefficients to the math module

kellerfuchs added the comment: @Raymond Hettinger > Let's name this comb() instead of binomial() please (as requested by me, > Mark, and Tim). (Replying here to keep the discussion in a single place.) As far as I can tell from the discussions here, Steven and you stated a preference for

[issue35431] Add a function for computing binomial coefficients to the math module

kellerfuchs added the comment: So, I rebased Yash's and my branches, and merged them together. The result is still in PR#11018. This involved a few changes, which seem to reflect the consensus here: - raise ValueError if k>n ; - rename the function to math.combinations. --

[issue35431] Add a function for computing binomial coefficients to the math module

kellerfuchs added the comment: > Start with an initial patch that implements this simplest possible > implementation, accompanied by clean documentation and thorough testing. > > Once everyone has agreed on the API (i.e. calling it "comb()", how to handle > various input datatypes, and

[issue35431] Add a function for computing binomial coefficients to the math module

kellerfuchs added the comment: Hi everyone, Sorry for the lack of reply, I severely underestimated how exhausting the holiday season would be. Catching up with the comments right now. -- ___ Python tracker

[issue35431] Add a function for computing binomial coefficients to the math module

Yash Aggarwal added the comment: @tim.peters Got it. -- ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue35431] Add a function for computing binomial coefficients to the math module

Tim Peters added the comment: Please resist pointless feature creep. The original report was about comb(n, k) for integer n and k with 0 <= k <= n and that's all. Everyone who commented appeared to agree they'd find that useful. But nobody has said they'd find generalizing beyond those

[issue35431] Add a function for computing binomial coefficients to the math module

Yash Aggarwal added the comment: @steven.daprano > Are you also providing a perm(n, k) function? I didn't know it is also being implemented. Should I start on that too? My implementation is based on these requirements: > - Spell it comb(n, k). > - TypeError if args aren't ints. > -

[issue35431] Add a function for computing binomial coefficients to the math module

Steven D'Aprano added the comment: > return (-1)**k * bincoeff(n+k+1, k) Oops, that's meant to be n+k-1. -- ___ Python tracker ___

[issue35431] Add a function for computing binomial coefficients to the math module

Steven D'Aprano added the comment: > should the function be expanded to calculate for negative > n or is the function expected to work only in combination sense? If this were my design, I would offer both but in separate functions: def comb(n, k): if n < 0: raise ValueError return

[issue35431] Add a function for computing binomial coefficients to the math module

Yash Aggarwal added the comment: I have written the function in the latest patch to work only for positive n. Although the definition of combination or nChoosek makes no sense for negative n, negative binomial distribution exists and so binomial coefficient is defined for negative value of

[issue35431] Add a function for computing binomial coefficients to the math module

Change by Yash Aggarwal : -- pull_requests: +10812 ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue35431] Add a function for computing binomial coefficients to the math module

Yash Aggarwal added the comment: Thanks @mark.dickinson. As @rhettinger suggested, I'll write a basic function that uses division and works in O(k) for now. It's holiday season but hopefully @kellerfuchs will respond by then, and in the meantime I'll write more tests other than pascal's

[issue35431] Add a function for computing binomial coefficients to the math module

Raymond Hettinger added the comment: Kellar and Yash, my suggestion is to separate the work into two phases. Start with an initial patch that implements this simplest possible implementation, accompanied by clean documentation and thorough testing. Once everyone has agreed on the API (i.e.

[issue35431] Add a function for computing binomial coefficients to the math module

Mark Dickinson added the comment: > Can I work on C implementation if no-one else is doing it right now? Sounds fine to me. You might want to coordinate with @kellerfuchs to see what the status of their PR is; maybe the two of you can collaborate? @kellerfuchs: are you still planning to

[issue35431] Add a function for computing binomial coefficients to the math module

Yash Aggarwal added the comment: Can I work on C implementation if no-one else is doing it right now? -- nosy: +FR4NKESTI3N ___ Python tracker ___

[issue35431] Add a function for computing binomial coefficients to the math module

Tim Peters added the comment: Just for fun, here's a gonzo implementation (without arg-checking) using ideas from the sketch. All factors of 2 are shifted out first, and all divisions are done before any multiplies. For large arguments, this can run much faster than a dumb loop. For

[issue35431] Add a function for computing binomial coefficients to the math module

Mark Dickinson added the comment: [Tim] > My two cents: > > - Spell it comb(n, k). > - TypeError if args aren't ints. > - ValueError if not 0 <= k <= n. +1 to all of this. -- ___ Python tracker

[issue35431] Add a function for computing binomial coefficients to the math module

Tim Peters added the comment: My two cents: - Spell it comb(n, k). - TypeError if args aren't ints. - ValueError if not 0 <= k <= n. Not concerned about speed. It's possible to do this with no divisions involving integers bigger than `n` and `k`(*), using O(k) space, but for "practical"

[issue35431] Add a function for computing binomial coefficients to the math module

Raymond Hettinger added the comment: > For what its worth, the colour I prefer for this bikeshed are > "comb" and "perm", which are the names used by the > HP 48GX calculator. Second choice would be to spell the names > out in full, "combinations" and "permutations". +1 These would be my

[issue35431] Add a function for computing binomial coefficients to the math module

Steven D'Aprano added the comment: Brett, what was the purpose of the title change? > title: The math module should provide a function for computing > binomial coefficients -> Add a function for computing binomial > coefficients to the math module --

[issue35431] Add a function for computing binomial coefficients to the math module

Change by Brett Cannon : -- title: The math module should provide a function for computing binomial coefficients -> Add a function for computing binomial coefficients to the math module ___ Python tracker