2

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.

1
  • 1
    Which python and bumpy version are you using? I don't see any negative numbers when running with python 2.7.5… It could be a 32bit problem. Ahm, I just noticed that 20 is the highest number which does not return a negative number.
    – tamasgal
    Aug 14, 2013 at 9:39

3 Answers 3

3

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]
4
  • I wasn't aware that the range function creates a list. Thanks!
    – TopGun
    Aug 14, 2013 at 10:30
  • np.prod(np.arange(1,21,dtype=np.uint64)) works just fine. You can also use floats for larger factorials, though they are not exact.
    – Daniel
    Aug 14, 2013 at 13:09
  • @Ophion So you can tell it to use a 64 bit int? Numpy is pretty awesome!
    – AlexJ136
    Aug 14, 2013 at 13:59
  • Yes, numpy will only change the dtype if the dtype is of int and the precision is less then the default platform integer precision.
    – Daniel
    Aug 14, 2013 at 14:16
1

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)
0

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))
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.