[issue2138] Add a factorial function

[Mark Dickinson]

Mark Dickinson <dickinsm at gmail.com> added the comment:

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.

__________________________________
Tracker <report at bugs.python.org>
<http://bugs.python.org/issue2138>
__________________________________