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