Add a factorial function

[fcca6e88-ce27-4e2d-b19d-c1f86a26968c]

BPO	2138
Nosy	@birkenfeld, @rhettinger, @terryjreedy, @mdickinson, @devdanzin

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields: ```python assignee = 'https://github.com/rhettinger' closed_at = created_at = labels = ['type-feature', 'library'] title = 'Add a factorial function' updated_at = user = 'https://bugs.python.org/dtorp' ``` bugs.python.org fields: ```python activity = actor = 'mark.dickinson' assignee = 'rhettinger' closed = True closed_date = closer = 'rhettinger' components = ['Library (Lib)'] creation = creator = 'dtorp' dependencies = [] files = [] hgrepos = [] issue_num = 2138 keywords = [] message_count = 35.0 messages = ['62520', '62534', '62535', '62536', '62539', '62541', '62549', '62551', '62552', '62553', '62555', '62557', '62674', '62691', '62707', '62729', '62761', '63805', '63816', '63818', '63822', '63823', '63828', '63961', '63969', '64913', '67571', '67572', '67583', '67588', '67859', '68355', '69831', '73278', '105605'] nosy_count = 13.0 nosy_names = ['georg.brandl', 'rhettinger', 'terry.reedy', 'jafo', 'phr', 'mark.dickinson', 'dtorp', 'alanmcintyre', 'ajaksu2', 'avalind', 'ilan', 'uzi', 'maix'] pr_nums = [] priority = 'normal' resolution = 'accepted' stage = None status = 'closed' superseder = None type = 'enhancement' url = 'https://bugs.python.org/issue2138' versions = ['Python 2.6'] ```

[fcca6e88-ce27-4e2d-b19d-c1f86a26968c]

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.

[a389c4e4-8cb0-45a1-9c34-18e4c9ac3050]

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. ;)

[mdickinson]

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?

[mdickinson]

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

[a389c4e4-8cb0-45a1-9c34-18e4c9ac3050]

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?

[mdickinson]

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.

[rhettinger]

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.

[mdickinson]

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?

[rhettinger]

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

[mdickinson]

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.

[rhettinger]

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

[fcca6e88-ce27-4e2d-b19d-c1f86a26968c]

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.

[91e69f45-91d9-4b12-87db-a02908296c81]

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.

[90baf024-6604-450d-8341-d796fe6858f3]

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

[d84e553d-3c75-4bfc-8719-add07ffee075]

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.

[mdickinson]

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.

[d84e553d-3c75-4bfc-8719-add07ffee075]

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.

[99f38442-44f2-410e-a40f-97b035e7d985]

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.

[rhettinger]

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.

[eacf80b2-9081-4882-a7f5-27e9644c3853]

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.

[rhettinger]

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.

[91e69f45-91d9-4b12-87db-a02908296c81]

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.

[rhettinger]

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.

[mdickinson]

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.

[rhettinger]

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

[terryjreedy]

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.

[3d3acb75-188d-4d0d-97b2-12d3e19fc968]

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.

[3d3acb75-188d-4d0d-97b2-12d3e19fc968]

Or slightly better:

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

[mdickinson]

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.

[rhettinger]

I've got in from here.

[rhettinger]

Added math.factorial() in r64050.

[mdickinson]

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

[birkenfeld]

That was fixed by Raymond in 64365.

[b296dd58-b8ad-4fc0-a325-facd225b0aae]

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.

[mdickinson]

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