Integer multiplication overflow.

Alex Martelli aleaxit at yahoo.com
Sun Oct 8 03:24:54 EDT 2000


<johnvert at my-deja.com> wrote in message news:8ronb6$75e$1 at nnrp1.deja.com...
> Hello,
>
> I wrote the following simple recursive factorial function in python:
>
> def fact(num):
>   if num < 2: 1
>   return num * fact(num - 1)
    [snip]
> >>> fact(15)
    [snip]
> Why is that?  If I compare this with the Scheme equivalent:
    [snip]
> and run it with MzScheme, I can do:
>
> > (fact 15)
> 1307674368000
    [snip]
> So why does python choke (pun intended) on a slightly large
> multiplication?  I know it's not meant to be very numeric (although I
> hear it's capable of a lot with the Numeric package,) but the factorial
> of 15 is trivial.

Python undecorated integers are fixnums (in scheme/lisp/fp terms) --
32-bit signed fixnums (that's somewhat larger than a typical lisp's
implementation fixnums, a range of about +/- 2 billions).  So, you're
getting an overflow error because the multiplication would have a
result that is over about 2 billions.  You'd have similar problems on
any language with a similar use of fixnums, of course (including
several lisp variants).

To avoid fixnums' limitations, use unbounded-length integers
instead.  In Python, these are denoted by appending an L to the
sequence of digits.  So, just change your function to:

>>> def fact(num):
 if num < 2: return 1L
 return num * fact(num - 1)

>>> fact(15)
1307674368000L

>>> fact(52)
80658175170943878571660636856403766975289505440883277824000000000000L


I'm not sure what you mean by Python being "not very numeric".
Quite apart from NumPy, I find it perfectly adequate for the
combinatorial arithmetic problems I often handle.  It doesn't
have unlimited-precision rationals in the language or standard
library (I don't know why -- it IS a strange omission) -- but
they're not hard to fit seamlessly (the ability to define every
arithmetic operator for a class helps).


Alex






More information about the Python-list mailing list