[Edu-sig] Speaking of factorials...

[Tim Peters]

[Kirby Urner]
> ...
> Oooo, fast machine.

866 Pentium -- a bit behind the times.  But I'm running what will eventually
become Python 2.2, and it's a bit faster than 2.1.

> Tomorrow I upgrade from this AMD 400 Mhz to a 1.2 Mhz AMD Thunderbird --

Cool!  Especially if you meant GHz <wink>.

> will retest for kicks.  But then, this is Windows.

Oh, same here -- Win98SE.  It's a pain for development work (& trying to
time things on it reliably is almost hopeless), but it keeps me much more
sympathetic to my sisters and the majority of Python's new users than I
would be otherwise.  Now I can dismiss complaints with *empathy* <wink>.

> ...
> Here's another version of goodcombo:
>
>    def goodcombo(n,k):
>        """
>        Returns n!/k!(n-k)! where n>=k
>        """
>        numer = reduce(mul,[1L]+range(n-k+1,n+1))
>        return numer/reduce(mul,[1L]+range(2,k+1))
>
> Works with long ints, but still slower than yours, and no
> parameter checking.  I see now that ending with that fatso
> division is less efficient than your "divide as you go"
> strategy.

That's especially true when working with long ints, and you already know
why!  Here's a big int:

    29837498239837948798274982794283749383279384

Forget computers for a moment:  would *you* rather divide that by 7, or by
3489798?  Python too.  The routine to divide by "a digit" is much simpler
than the routine to divide by "a whole bunch of digits".  Sophisticated
bigint packages don't care so much, but Python's was written for correctness
and portability rather than for peak speed.

BTW, "a digit" in the bigint internals is actually in range(2**15), so
Python is as happy to divide by 27777 as by 7.  Go over that boundary,
though, and speed takes a hit.  The comb() routine first divides by 2, then
by 3, etc, so in practice never needs to do "a fancy" division.

When you're working with small ints, though, the hardware is doing the
division and it doesn't care so much.  If you time it, you'll often find
that reduce() is slower than an equivalent loop.

> ...
> comb is well-designed.

Thanks!  It was part of an Industrial Package, so it had to be <wink>.

> Like your _chop method too -- great stuff!

Scheme has it all over Python there:  it's a PITA that Python has more than
one flavor of int!  We're slowly moving toward eradicating the user-visible
difference.  It's slow going, though, because it's hard to do it in a way
that's 100% backward compatible; sooner or later I'm afraid we're going to
have to break some old code.