Add a factorial function

[dtorp]

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:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2008-06-09.06:55:31.132>
created_at = <Date 2008-02-18.10:09:27.896>
labels = ['type-feature', 'library']
title = 'Add a factorial function'
updated_at = <Date 2010-05-12.19:57:34.307>
user = 'https://bugs.python.org/dtorp'

bugs.python.org fields:

activity = <Date 2010-05-12.19:57:34.307>
actor = 'mark.dickinson'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2008-06-09.06:55:31.132>
closer = 'rhettinger'
components = ['Library (Lib)']
creation = <Date 2008-02-18.10:09:27.896>
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']

[dtorp]

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.

[alanmcintyre]

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

[alanmcintyre]

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.

[dtorp]

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.

[phr]

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.

[devdanzin]

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

[avalind]

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.

[avalind]

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.

[ilan]

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.

[jafo]

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.

[phr]

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.

[uzi]

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.

[uzi]

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.

[maix]

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.