combination function in python

[Steven D'Aprano]

On Sun, 15 Apr 2007 13:58:38 -0700, Mark Dickinson wrote:

> ... for large n and k it's difficult to imagine any real-world
> applications that wouldn't be better served by using the lngamma
> function instead.  That is, the natural log of n choose k can be
> computed much more quickly as
> 
> lngamma(n+1) - lngamma(k+1) - lngamma(n-k+1)

Yes, but if you actually want the number of combinations, not the log of
the number of combinations, you then have to raise e to that power to get
the answer you want -- and that takes time. Is it still faster? How about
round-off error due to floating point? Should you be truncating or
rounding? What about overflow error for large enough n, k?

What exactly are we doing with a five hundred digit long integer anyway?

Exact (long) integer maths still is useful.


> I assume that lngamma is implemented somewhere in either numpy or
> scipy, but right now I can't find it...

You know what they say about what happens when you ASS_U_ME :-)


-- 
Steven.