Repository navigation
Add a factorial function #46391
Description
| 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']
Activity
dtorp commentedon Feb 18, 2008
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 commentedon Feb 18, 2008
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 commentedon Feb 18, 2008
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 commentedon Feb 18, 2008
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 commentedon Feb 18, 2008
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 commentedon Feb 18, 2008
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 commentedon Feb 18, 2008
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 commentedon Feb 18, 2008
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 commentedon Feb 18, 2008
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 commentedon Feb 18, 2008
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 commentedon Feb 19, 2008
I wouldn't worry about that so much -- our job is to provide good
primitives.
dtorp commentedon Feb 19, 2008
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:
When the assertions are turned-off, this runs pretty fast.
phr commentedon Feb 22, 2008
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.
17 remaining items
terryjreedy commentedon Apr 4, 2008
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 commentedon May 31, 2008
It's a simplified version, but why not something like this:
A product() function could also be done similarly.
uzi commentedon May 31, 2008
Or slightly better:
mdickinson commentedon May 31, 2008
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 commentedon May 31, 2008
I've got in from here.
rhettinger commentedon Jun 9, 2008
Added math.factorial() in r64050.
mdickinson commentedon Jun 18, 2008
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:
birkenfeld commentedon Jul 16, 2008
That was fixed by Raymond in 64365.
maix commentedon Sep 15, 2008
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 commentedon May 12, 2010
maix: good point. Fixed in revisions r81126 through r81129.