Calculating factorial

[Tim Hochberg]

"Alex Martelli" <aleaxit at yahoo.com> wrote in message
news:90ib2e0216k at news2.newsguy.com...
> "Joshua Muskovitz" <josh at open.com> wrote in message
> news:3a2c8c2a_3 at corp.newsfeeds.com...
> > What about using xrange() instead of range() to support *really* large
> > numbers?
>
> Of marginal usefulness in the context of computing factorials.

I agree that in practice, but to be nitpicky, in theory it does matter.

> The memory space taken by a number X grows, roughly, with the
> logarithm of X.  From Stirling's formula, we know that
>     log(N!) about= N log(N) - N
> for large N; for N large enough, this means that N! takes up
> memory space growing as O(N logN).

Agreed.

> Since range(N) takes up memory space growing as O(N), for a
> large enough N this memory consumption becomes irrelevant
> compared to the memory which N! itself takes up.

This is not true. If range supported long integers, for _really_ large N,
range(N) would take up O(sum(log i))=O(log(N!)) memory space. So it would
take up the same memory space as N!. However, since N is limited to
sys.maxint, and since the integers in range always take log(sys.maxint)
space, range(N) actually takes up O(N log sys.maxint) memory which is always
larger than the O(N log N) take by N!.

> There _may_ be a value or two of N such that you have just
> enough memory to compute N! if you carefully husband every
> little bit, which is why the usefulness of xrange is
> "marginal" rather than "non-existent".  But I doubt you'd
> want to wait for the computation times needed for such
> calculations on a typical machine of today (with a few
> hundreds megabytes and several hundreds Meaningless
> Instructions Per Second), particularly with the multiplication
> algorithm that is used by Python's builtin 'long integer'
> numbers.

This is why I agree that range is most likely best in practice.

[SNIP]

-tim