Author mark.dickinson
Recipients belopolsky, mark.dickinson, rhettinger, stutzbach
Date 2010-05-11.23:20:35
SpamBayes Score 0.000131924
Marked as misclassified No
Message-id <AANLkTinOsDIIBV-iBZn6b8JFkX8vtkmFIDn4OjJaqmEE@mail.gmail.com>
In-reply-to <1273617211.59.0.766982968625.issue8692@psf.upfronthosting.co.za>
Content
On Tue, May 11, 2010 at 11:33 PM, Alexander Belopolsky
<report@bugs.python.org> wrote:
> It seems to me that the value of n for which number of digits will exceed sys.maxsize can be estimated fairly accurately using Stirling formula.  Only two values are relevant in practice - one for sys.maxsize = 2**63-1 and the other for sys.maxsize = 2**31-1.  These values can be hardcoded and factorial can quickly report the case when n! will exceed maxsize digits instead of hanging until memory is exhausted.

Sure, bailing out for ridiculously large arguments sounds fine to me.
On a 64-bit machine, there can be at most 2**61 4-byte digits, each
digit giving containing 30 bits of the long.  So the maximum
representable long (under the implausible assumption that someone
could actually find 2**63 bytes of storage) would be around
2**(30*2**61).  The following quick search gives me a value of around
1.18e18 for the first n such that n! exceeds this value:

from math import log, lgamma

def bisect(f, a, b):
    c = (a + b)/2.0
    while a != c and b != c:
        a, b = (a, c) if f(c) else (c, b)
        c = (a + b)/2.0
    return c

BOUND = 2**62*15*log(2)
print(bisect(lambda x: lgamma(x) > BOUND, 2.0, 1e30))
History
Date User Action Args
2010-05-11 23:20:55mark.dickinsonsetrecipients: + mark.dickinson, rhettinger, belopolsky, stutzbach
2010-05-11 23:20:52mark.dickinsonlinkissue8692 messages
2010-05-11 23:20:35mark.dickinsoncreate