Negative numbers returned in a factorial Function (Python)

Question

I have the following code to calculate n!

import numpy as np

print "n! (for n<31)"
print

n = input("Enter n: ")

lst = []
for i in range(1,n+1):
    lst.append(i)

print lst     #Just to see if the program is working

print "n!: ", np.prod(lst)

However, for some numbers, the program returns a negative value.

Eg. The following is from the console when I ran it for n = 20:

n! (for n<31)

Enter n: 20
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
n!:  -2102132736

It also happens for n = 32 However, the program does work for other numbers, eg. 3! returns 6, as it should.

Can someone please explain.

Answer 1

As I wrote in my comment, it's a 32bit problem. If you have a 64bit system, you can still calculate up to 20!

Here is a solution without numpy, with the python builtin types, which handle such problems pretty safely:

def factorial(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result

n = input("n! (for n<31)\n\nEnter n: ")
print("n!: %d" % factorial(n))

And here is a recursive function to bend your mind ;-)

def factorial_r(n):
    if n < 2:
        return 1
    return n * factorial_r(n-1)

n = input("n! (for n<31)\n\nEnter n: ")
print("n!: %d" % factorial_r(n))

Answer 2

Here's a link to the documentation for numpy's prod function:

numpy.prod

If you go to the bottom of that page, you'll see the very last example says that when x (the given parameter to the function) is an unsigned integer, the result that gets returned is a default platform integer. So numpy will not convert the result into a long type when the result exceeds that which can be stored in a 32 bit integer, like python usually does. So you are getting integer overflow.

if you declare a function:

def fact(n): return 1 if n == 1 else (n * fact(n-1))

and do:

fact(20)

you get:

2432902008176640000L

which is the correct value for 20!.

By the way, doing:

lst = []
for i in range(1,n+1):
    lst.append(i)

is not ideal. Python's range function can do this easily! try:

lst = range(1, n + 1)

You're already doing this in your for-loop! You can test it in the interpreter:

>>> range(1, 20 + 1)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

Answer 3

I strongly suspect Numpy is creating an array of 32-bit ints.

Therefore you are seeing integer overflow when n! is greater than the limit of a 32 bit integer.

try:

 print "n!: ", np.prod(lst, dtype=np.uint64)