Integer multiplication overflow.

[Fredrik Lundh]

"johnvert" wrote:
> I wrote the following simple recursive factorial function in python:
> 
> def fact(num):
>   if num < 2: 1
>   return num * fact(num - 1)
> 
> When I run it, I get the following:
> 
> >>> fact(3)
> 6

note that with the code you posted, you're more likely to get
a RuntimeError (Maximum recursion depth exceeded).

> 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.

not if you're a 32-bit computer ;-)

:::

unlike scheme, python doesn't automatically change from
ordinary (machine) integers to long (unlimited precision)
integers.  (maybe in "python 3000"...)

as others have pointed out, you can use long integers from
the start:

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

it can sometimes be more efficient to switch only when necessary:

    def fact(num):
        if num < 2:
            return 1
        tail = fact(num - 1)
        try:
            return num * tail
        except OverflowError:
            return long(num) * tail

:::

btw, here's a version for people who have problems pressing the
return key:

    def fact(num): return long(num < 2) or num * fact(num - 1)

</F>

<!-- (the eff-bot guide to) the standard python library:
http://www.pythonware.com/people/fredrik/librarybook.htm
-->