math.factorial may throw OverflowError

[ncoghlan]

BPO	20539
Nosy	@mdickinson, @ncoghlan, @pitrou, @vstinner, @skrah, @gareth-rees, @MojoVampire
Files	huge_factorial_input.patch huge_factorial_input_v2.patch huge_factorial_input_v3.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/mdickinson'
closed_at = <Date 2014-04-10.13:35:30.993>
created_at = <Date 2014-02-07.10:54:29.109>
labels = ['extension-modules', 'type-bug']
title = 'math.factorial may throw OverflowError'
updated_at = <Date 2014-04-10.13:35:30.991>
user = 'https://github.com/ncoghlan'

bugs.python.org fields:

activity = <Date 2014-04-10.13:35:30.991>
actor = 'mark.dickinson'
assignee = 'mark.dickinson'
closed = True
closed_date = <Date 2014-04-10.13:35:30.993>
closer = 'mark.dickinson'
components = ['Extension Modules']
creation = <Date 2014-02-07.10:54:29.109>
creator = 'ncoghlan'
dependencies = []
files = ['33961', '33965', '34777']
hgrepos = []
issue_num = 20539
keywords = ['patch']
message_count = 29.0
messages = ['210448', '210449', '210450', '210451', '210453', '210454', '210455', '210477', '210480', '210496', '210497', '210510', '210511', '210512', '210513', '210528', '210555', '210571', '215842', '215847', '215852', '215857', '215861', '215862', '215869', '215873', '215877', '215879', '215881']
nosy_count = 9.0
nosy_names = ['mark.dickinson', 'ncoghlan', 'pitrou', 'vstinner', 'skrah', 'python-dev', 'gdr@garethrees.org', 'garybernhardt', 'josh.r']
pr_nums = []
priority = 'low'
resolution = 'fixed'
stage = None
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue20539'
versions = ['Python 3.5']

[ncoghlan]

I believe this is mostly a curiousity (since actually calculating a factorial this big would take an interminable amount of time), but math.factorial can be provoked into throwing OverflowError by a large enough input:

>>> math.factorial(10**19)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: Python int too large to convert to C long

>>> math.factorial(1e19)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: Python int too large to convert to C long

[mdickinson]

What behaviour would you suggest instead?

Apart from the time, the result would have over 10**20 digits, so would need exabytes of memory to represent.

>>> from math import lgamma, log
>>> lgamma(1e19) / log(10)
1.8565705518096748e+20

[vstinner]

What behaviour would you suggest instead?

Some others Python functions like str * int raises a MemoryError on overflow.

But I don't know if OverflowError or MemoryError is better.

[mdickinson]

Some others Python functions like str * int raises a MemoryError on overflow.

I have to say that that's always seemed wrong to me: IMO MemoryError should only be raised when we've really run out of memory, or perhaps where the amount of memory we're about to need exceeds all possible limits (e.g., more than 2**63 bytes on a 64-bit system).

[skrah]

OverflowError seems like a good choice if only values in the range
of a C long are accepted. ValueError would perhaps be more intuitive,
since the user normally only cares about the accepted range of
input values rather than the internal details.

[ncoghlan]

I figured it was some internal storage overflowing, and I don't have an issue with the error type. The bit that is confusing is the error *message* - what int doesn't fit into a C long? (especially in the second case of float input where no user level int is involved at all).

It's mostly a theoretical problem though - as far as I am aware, the user that hit it was deliberately testing how far the limits of the "infinite precision" integers promised in the documentation actually extend.

[mdickinson]

The bit that is confusing is the error *message* - what int doesn't fit into a C long?

Agreed: it would be nice to intercept this and give a better message.

[pitrou]

I also think OverflowError is better than MemoryError here.

[gareth-rees]

It's not a case of internal storage overflowing. The error is from
Modules/mathmodule.c:1426 and it's the input 10**19 that's too large
to convert to a C long. You get the same kind of error in other
places where PyLong_AsLong or PyLong_AsInt is called on a
user-supplied value, for example:

    >>> import pickle
    >>> pickle.dumps(10**19, 10**19)
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    OverflowError: Python int too large to convert to C long

[mdickinson]

Thinking about it, ValueError seems like the right exception type: nothing's actually overflowing, because we haven't even tried to do any computation. This is just a limitation of what math.factorial is prepared to accept as input (and perhaps that limitation should be documented).

Here's a patch. Bikeshedding about the exception type and the exception message is welcome.

[vstinner]

OverflowError makes sense because math.factorial(10**19) will overflow in CPython on common platforms, even if it didn't overflowed yet.

On a supercomputer with a different Python implementation, you may be able to compute it.

IMO An OverflowError is specific to a platform and Python implementation, whereas ValueError is "portable": any Python implementation must raise such error.

I can imagine that a Python implementation may return a pseudo-int type which is supposed to be the result of math.factorial(), so you can compute for example math.factorial(10**19) % 2 (hint: result is 0).

[mdickinson]

Okay; OverflowError seems to have the majority vote. I'll change it to that.

Any strong opinions on the message?

[pitrou]

"Outrageously" sounds like the argument is immoral, but do we have an objective test for that? :-)

(nitpicking a bit: negative values should probably raise a proper ValueError, no?)