Issue2138

Created on **2008-02-18 10:09** by **dtorp**, last changed **2010-05-12 19:57** by **mark.dickinson**. This issue is now **closed**.

Messages (35) | |||
---|---|---|---|

msg62520 - (view) | Author: David Albert Torpey (dtorp) | Date: 2008-02-18 10:09 | |

Add a factorial method. Everybody understands what it means before they are out of high school and it comes up all the time in statistics and combinatorics. Ruby has a factorial method and heck even basic calculators have a factorial key. print n.factorial() Maybe raise ValueError if n is negative. |
|||

msg62534 - (view) | Author: Alan McIntyre (alanmcintyre) | Date: 2008-02-18 15:43 | |

It seems like most of the methods on integers are for two-argument operations (add, mul, div, etc.), while a lot of single-argument operations are in the math module. If this gets added would it fit better as a function in the math module? I have to say a factorial function is something I've found myself writing several times, so I certainly wouldn't mind having one included. Yeah, it's a one-liner, but so is hypot, and that's already in the stdlib. And most calculators don't have a hypot button. ;) |
|||

msg62535 - (view) | Author: Mark Dickinson (mark.dickinson) * | Date: 2008-02-18 15:46 | |

I don't think it would be appropriate to add this as a method of int; it seems like unnecessary clutter on a core type. Perhaps a math.factorial function could be considered? Historically, the math module has just been a way to wrap the (mostly floating-point) libm functions, but I think that may be changing: there's at least some interest in putting gcd into the math module, for example. David, any chance you could come up with a patch implementing math.factorial? |
|||

msg62536 - (view) | Author: Mark Dickinson (mark.dickinson) * | Date: 2008-02-18 15:48 | |

> Yeah, it's a one-liner, but so is hypot Except that hypot is not a one-liner, if you want to get edge cases right. (Consider hypot(1e200, 1e200), or hypot(1e-200, 1e-200).) |
|||

msg62539 - (view) | Author: Alan McIntyre (alanmcintyre) | Date: 2008-02-18 17:50 | |

>Except that hypot is not a one-liner, if you want to get edge cases right. Ah, true; thanks for pointing that out. Should there be some upper limit on the argument math.factorial would take? At the moment I can't think of any reason for picking a given limit, except perhaps execution time. (10**4)! can be done in about 1 second on my old & slow laptop; are there realistic use cases for numbers much bigger than that? |
|||

msg62541 - (view) | Author: Mark Dickinson (mark.dickinson) * | Date: 2008-02-18 18:12 | |

> Should there be some upper limit on the argument math.factorial would take? I'd say not. Any such limit would be artificial, and an arbitrary choice. Just let the natural time and space requirements be the limiting factor. |
|||

msg62549 - (view) | Author: Raymond Hettinger (rhettinger) * | Date: 2008-02-18 22:40 | |

Since the domain and range are ints/longs, this makes more sense as a method on <type 'int'> than as a math module function. The other math module functions mostly have real valued inputs and mostly have counterparts in cmath. IIRC, Tim wanted the math module to maintain that theme and not become a home to every function that seems a bit "mathematical". I share the sentiment -- it would be nice for the math module to retain its unified theme during its growth spurt. |
|||

msg62551 - (view) | Author: Mark Dickinson (mark.dickinson) * | Date: 2008-02-18 22:55 | |

> Since the domain and range are ints/longs, this makes more sense as a > method on <type 'int'> than as a math module function. Fair enough. Raymond, do you have any thoughts on where a gcd implementation might most usefully live? Should it stay in fractions.py, or is there a case for moving it somewhere more central? |
|||

msg62552 - (view) | Author: Raymond Hettinger (rhettinger) * | Date: 2008-02-18 23:04 | |

gcd() is probably fine where it is. People learn about GCD and LCM where they first learn fractions. So, there is a strong association. |
|||

msg62553 - (view) | Author: Mark Dickinson (mark.dickinson) * | Date: 2008-02-18 23:05 | |

The other issue here is that I see factorial as being the thin end of the wedge. If factorial were implemented, it would probably only be on the order of minutes before people wanted to know where the binomial() function was. So it seems to me that either there should be a good single place for all integer-related math, (gcd, xgcd, binomial, factorial, ...) or we should leave this for third-party modules for the moment. |
|||

msg62555 - (view) | Author: Raymond Hettinger (rhettinger) * | Date: 2008-02-19 02:39 | |

I wouldn't worry about that so much -- our job is to provide good primitives. |
|||

msg62557 - (view) | Author: David Albert Torpey (dtorp) | Date: 2008-02-19 08:28 | |

Mr. Dickinson thank you for doing this. I do not know how to help with a patch. If it helps, here is the code I use in python: def factorial(n, _known=[1]): assert isinstance(n, int), "Need an integer. This isn't a gamma" assert n >= 0, "Sorry, can't factorilize a negative" assert n < 1000, "No way! That's too large" try: return _known[n] except IndexError: pass for i in range(len(_known), n+1): _known.append(_known[-1] * i) return _known[n] When the assertions are turned-off, this runs pretty fast. |
|||

msg62674 - (view) | Author: paul rubin (phr) | Date: 2008-02-22 03:53 | |

I like the idea of having some integer math functions like this in the stdlib; whether in the math module or elsewhere doesn't matter much. In particular I remember having to implement xgcd on several separate occasions for unrelated applications, each time requiring about the same head scratching as before, and wishing it was in the stdlib so that could be avoided. This type of function is complicated enough to not rattle immediately off the fingertips, but not complicated enough to be worth looking up in a reference book. http://bugs.python.org/issue457066 has some discussion of xgcd and modular inverses. |
|||

msg62691 - (view) | Author: Daniel Diniz (ajaksu2) | Date: 2008-02-22 15:47 | |

Would it be implemented in C? How about using Luschny's Prime Swing (http://www.luschny.de/math/factorial/FastFactorialFunctions.htm and http://www.luschny.de/math/factorial/Benchmark.html )? |
|||

msg62707 - (view) | Author: Anders Valind (avalind) | Date: 2008-02-22 23:20 | |

IMHO, The best place to put functions such as xgcd, factorial, etc, would be a new imath module, an integer equivalent of cmath. Not only would it keep the standard math module clean, it would also make clear that these functions are for integers only. |
|||

msg62729 - (view) | Author: Mark Dickinson (mark.dickinson) * | Date: 2008-02-23 13:58 | |

The trouble is that this comes at a time when people are trying to trim the standard library down rather than enlarge it. Perhaps the solution is a high-quality third party 'imath' module? If/when it gets to a stage where lots of people are using it, it could be considered for inclusion in the std. lib. |
|||

msg62761 - (view) | Author: Anders Valind (avalind) | Date: 2008-02-23 16:06 | |

Yeah, I like the idea of a third party module and letting the popularity and quality decide when/if it will be included. This would also make it easier to see what kind of functionality people would want. |
|||

msg63805 - (view) | Author: Ilan Schnell (ilan) * | Date: 2008-03-17 23:18 | |

The factorial function is most likely to be used in context with other combinatorial functions (like binomial coefficients) for these functions an external module seems most appropriate. Most likely people would use a factorial function only for some small toy calculation, for those cases one can always roll a factorial function oneself. Python should therefore not be cluttered with this function. I discussed this with several developers at PyCon08, and have therefore decided to close the discussion for now. |
|||

msg63816 - (view) | Author: Raymond Hettinger (rhettinger) * | Date: 2008-03-18 00:27 | |

FWIW, I don't agree with the reasoning on the rejection. Hundreds of calculator layouts and school textbooks suggest that you can have a useful factorial function without having to also add binomials and whatnot. The OP requested a simple, widely understood integer method with no arguments. That seems very reasonable to me. A function or method is not clutter if it has widespread uses and a near zero learning curve. This is a re-invented function and it would be ashamed to not offer it because it is a pita every time you need it and it's not already there. My guess is that half of long-term Python programmers have written their own variant at some point but only a small percentage of those went on to write a binomial coeffient function. Eventhough this is re-invented often, it is not often re-invented well (i.e. good error messages for non-integer or negative inputs, a fast implementation with pre-computed values for small inputs, and being attached to a namespace where you can find it when needed). To compare, I checked the somewhat clean SmallTalk Integer API and found it had factorial, gcd, and lcm, but not the other functions mentioned in the thread. See: http://www.csci.csusb.edu/dick/samples/smalltalk.methods.html#Integer%20methods Re-opening for further discussion. If someone still feels that it is a bad idea, then go ahead and re-close; otherwise, I think we ought to accept this guy's request. |
|||

msg63818 - (view) | Author: Sean Reifschneider (jafo) * | Date: 2008-03-18 00:31 | |

Raymond: Can you come into the core sprint and discuss it with the table on the right just as you come in the door of the sprint room? Lian said that was who he discussed it with and they came to the conclusion to reject it. |
|||

msg63822 - (view) | Author: Raymond Hettinger (rhettinger) * | Date: 2008-03-18 00:36 | |

Wish I could be at the sprint. I'm back in Los Angeles. My little post will have to suffice. I thought it was a reasonable request and would hate to see it killed because other people piled on other requests that were not reasonable. I don't buy the reasoning that you have to reject factorial just because someone else might someday want binomial or a gamma. |
|||

msg63823 - (view) | Author: paul rubin (phr) | Date: 2008-03-18 00:37 | |

Rather than factorial how about a product function, so factorial(n) = product(xrange(1,n+1)). I do like the idea of an imath module whether or not it has factorial, and the topic of this rfe has drifted somewhat towards the desirability of such a module, which is a reasonable question for discussion. I'm more or less indifferent to whether imath has factorial in it or not. I do think it would be useful for it to have functions for things like binomial coefficients that were implemented a little more cleverly than with large factorials, but in this case factorial should be there too. |
|||

msg63828 - (view) | Author: Raymond Hettinger (rhettinger) * | Date: 2008-03-18 00:47 | |

Problems with product(): It is dreadfully inefficient compared to a good implementation of factorial. It has the same name a new itertool with much different functionality. The hyper-generalization takes us further away from the OP's dirt simple request for a piece of functionality that is widely understood, frequently reimplemented, and has a near zero learning curve. If his request is accepted, it does not preclude you from making some other module with tons of functions of interest to encryption people, number theorists, and statisticians. |
|||

msg63961 - (view) | Author: Mark Dickinson (mark.dickinson) * | Date: 2008-03-18 18:38 | |

I'm not opposed to adding factorial somewhere, and it doesn't seem as though anyone else is actively opposed to factorial either. The problem is working out where best to put it. To my inexperienced eyes, it feels wrong to add it as an int/long method, though I'm having trouble figuring out exactly why it feels wrong. It doesn't fit well with the stuff in the math module either, as Raymond has pointed out. There are other integer -> integer functions that I'd consider just as fundamental and useful as factorial, for a programming language that has arbitrary-precision integers. Examples are the integer square root (i.e. int(floor(sqrt(n)))), or the number of bits in an integer (int(floor(log(n, 2))). I've needed both of these much more often than factorial. If the powers that be accepted a request to add such functions, would they also naturally become integer methods? And supposing that gcd were added some day, shouldn't it be in the same place as factorial? As to implementation, I'd probably avoid PrimeSwing on the basis that the added complexity, and cost for future maintainers, just isn't worth it. The usual recursive algorithm (writing n! as (n*(n-2)*(n-4)*...) * ((n-1)*(n-3)*...), and then applying similar breakdowns to the subproducts) is probably good enough, together with some caching of small results. I can volunteer to try to implement this sometime before the 2.6/3.0 betas. |
|||

msg63969 - (view) | Author: Raymond Hettinger (rhettinger) * | Date: 2008-03-18 19:18 | |

I prefer factorial as a method (like Ruby and Smalltalk). Given the usual notation (n!) or pronounciation (n factorial), it is natural to write this as: n.factorial(). Compared to numbits() and isqrt(), a factorial() method is more basic in that it is self explanatory and everyone knows what it means by the time they are in middle school. FWIW, if separate RFEs were opened for numbits() and isqrt(), I would support their being int methods too. Their implementations are helped by access to the underlying representation, and a case could be made that these no argument calls are just properties of the number (just like the sign bit). |
|||

msg64913 - (view) | Author: Terry J. Reedy (terry.reedy) * | Date: 2008-04-04 04:59 | |

The fact that other languages have factorial does not in itself impress me. What is the actual use case other than illustrating computational induction (whether by iteration or recursion) and for calculating binomial coefficients? I don't really like the idea of making factorial a method for the same reason that exp, sin, ....... are not methods of float: there is no end. People should be able to learn basic classes without specialized functions attached. |
|||

msg67571 - (view) | Author: Joshua Uziel (uzi) | Date: 2008-05-31 10:33 | |

It's a simplified version, but why not something like this: import operator def factorial(num): return reduce(operator.mul, range(1, num+1)) A product() function could also be done similarly. |
|||

msg67572 - (view) | Author: Joshua Uziel (uzi) | Date: 2008-05-31 10:40 | |

Or slightly better: from operator import mul def factorial(num): return reduce(mul, range(2, num+1), 1) |
|||

msg67583 - (view) | Author: Mark Dickinson (mark.dickinson) * | Date: 2008-05-31 15:34 | |

Contrary to what I said above, I'm not going to find time for this before the beta. Anyone else want to have a go at producing a patch? A simple implementation would be fine---the algorithm could be tweaked for speed later. |
|||

msg67588 - (view) | Author: Raymond Hettinger (rhettinger) * | Date: 2008-05-31 20:22 | |

I've got in from here. |
|||

msg67859 - (view) | Author: Raymond Hettinger (rhettinger) * | Date: 2008-06-09 06:55 | |

Added math.factorial() in r64050. |
|||

msg68355 - (view) | Author: Mark Dickinson (mark.dickinson) * | Date: 2008-06-18 00:02 | |

It looks like there's a refcounting bug in the code: if the call to PyNumber_Multiply fails then iobj gets DECREF'd twice. This means that a keyboard interrupt of factorial() can exit the interpreter: Python 2.6a3+ (trunk:64341M, Jun 17 2008, 13:19:01) [GCC 4.0.1 (Apple Inc. build 5465)] on darwin Type "help", "copyright", "credits" or "license" for more information. >>> from math import factorial [36374 refs] >>> factorial(10**9) ^CFatal Python error: /Users/dickinsm/python_source/trunk/Modules/mathmodule.c:562 object at 0x81f63c has negative ref count -1 Abort trap |
|||

msg69831 - (view) | Author: Georg Brandl (georg.brandl) * | Date: 2008-07-16 20:53 | |

That was fixed by Raymond in 64365. |
|||

msg73278 - (view) | Author: (maix) | Date: 2008-09-15 17:48 | |

I think the unit test is wrong, or at least not as is intended: You put some numbers in values and shuffle them. But you don't use them but just range(10) for testing. |
|||

msg105605 - (view) | Author: Mark Dickinson (mark.dickinson) * | Date: 2010-05-12 19:57 | |

maix: good point. Fixed in revisions r81126 through r81129. |

History | |||
---|---|---|---|

Date | User | Action | Args |

2010-05-12 19:57:34 | mark.dickinson | set | messages: + msg105605 |

2008-09-15 17:48:38 | maix | set | nosy:
+ maix messages: + msg73278 |

2008-07-16 20:53:54 | georg.brandl | set | nosy:
+ georg.brandl messages: + msg69831 |

2008-06-18 00:02:03 | mark.dickinson | set | messages: + msg68355 |

2008-06-09 06:55:31 | rhettinger | set | status: open -> closed resolution: accepted messages: + msg67859 |

2008-05-31 20:22:04 | rhettinger | set | assignee: mark.dickinson -> rhettinger messages: + msg67588 |

2008-05-31 15:37:31 | mark.dickinson | set | assignee: mark.dickinson |

2008-05-31 15:34:50 | mark.dickinson | set | messages: + msg67583 |

2008-05-31 10:40:51 | uzi | set | messages: + msg67572 |

2008-05-31 10:33:33 | uzi | set | nosy:
+ uzi messages: + msg67571 |

2008-04-04 04:59:58 | terry.reedy | set | nosy:
+ terry.reedy messages: + msg64913 |

2008-03-18 19:18:37 | rhettinger | set | messages: + msg63969 |

2008-03-18 18:38:00 | mark.dickinson | set | messages: + msg63961 |

2008-03-18 00:47:24 | rhettinger | set | messages: + msg63828 |

2008-03-18 00:37:53 | phr | set | messages: + msg63823 |

2008-03-18 00:36:09 | rhettinger | set | messages: + msg63822 |

2008-03-18 00:31:24 | jafo | set | nosy:
+ jafo messages: + msg63818 |

2008-03-18 00:27:21 | rhettinger | set | status: closed -> open resolution: rejected -> (no value) messages: + msg63816 |

2008-03-17 23:18:36 | ilan | set | status: open -> closed title: Factorial -> Add a factorial function nosy: + ilan messages: + msg63805 priority: normal components: + Library (Lib), - Interpreter Core resolution: rejected |

2008-02-23 16:06:39 | avalind | set | messages: + msg62761 |

2008-02-23 13:58:27 | mark.dickinson | set | messages: + msg62729 |

2008-02-22 23:20:58 | avalind | set | nosy:
+ avalind messages: + msg62707 |

2008-02-22 15:47:05 | ajaksu2 | set | nosy:
+ ajaksu2 messages: + msg62691 |

2008-02-22 03:53:03 | phr | set | nosy:
+ phr messages: + msg62674 |

2008-02-19 08:28:10 | dtorp | set | messages: + msg62557 |

2008-02-19 02:39:07 | rhettinger | set | messages: + msg62555 |

2008-02-18 23:05:52 | mark.dickinson | set | messages: + msg62553 |

2008-02-18 23:04:30 | rhettinger | set | messages: + msg62552 |

2008-02-18 22:55:26 | mark.dickinson | set | messages: + msg62551 |

2008-02-18 22:40:58 | rhettinger | set | nosy:
+ rhettinger messages: + msg62549 |

2008-02-18 18:12:19 | mark.dickinson | set | messages: + msg62541 |

2008-02-18 17:50:51 | alanmcintyre | set | messages: + msg62539 |

2008-02-18 15:48:30 | mark.dickinson | set | messages: + msg62536 |

2008-02-18 15:46:09 | mark.dickinson | set | nosy:
+ mark.dickinson messages: + msg62535 |

2008-02-18 15:43:47 | alanmcintyre | set | nosy:
+ alanmcintyre messages: + msg62534 |

2008-02-18 10:09:27 | dtorp | create |