Unable to make a factorial function in Python

Question

My code

import sys

number=int(sys.argv[1])

if number == 0
    fact=1
else
    fact=number
for (x=1; x<number; x++)
    fact*=x;             // mistake probably here

print fact

I get the error

File "factorial.py", line 5
    if number == 0
                 ^
SyntaxError: invalid syntax

How can you make a factorial function in Python?

Answer 1

The line that your error is on should read

if number == 0:

Note the colon on the end.

Additionally, you would need to add the same colon after the else and the for. The colons work similarly to {} in other languages.

Finally, thats not how for loops work in Python. The code you want to use that list would be

for x in range(1,number):

Which would have the same effect of what you wrote, if you put that in a C style language.

EDIT: Oops, the for loop I gave was wrong, it would have included 0. I updated the code to correct this.

Answer 2

Here's your code, fixed up and working:

import sys
number = int(sys.argv[1])
fact = 1
for x in range(1, number+1):
    fact *= x

print fact

(Factorial zero is one, for anyone who didn't know - I had to look it up. 8-)

You need colons after if, else, for, etc., and the way for works in Python is different from C.

Answer 3

Here's a functional factorial, which you almost asked for:

>>> def fact(n): return reduce (lambda x,y: x*y, range(1,n+1))
... 
>>> fact(5)
120

It doesn't work for fact(0), but you can worry about that outside the scope of fact :)

---

Masi has asked whether the functional style is more efficient than Richie's implementation. According to my quick benchmark (and to my surprise!) yes, mine is faster. But there's a couple things we can do to change.

First, we can substitute lambda x,y: x*y with operator.mul as suggested in another comment. Python's lambda operator comes with a not-insignificant overhead. Second, we can substitute xrange for range. xrange should work in linear space, returning numbers as necessary, while range creates the whole list all at once. (Note then, that you almost certainly must use xrange for an excessively large range of numbers)

So the new definition becomes:

>>> import operator
>>> def fact2(n): return reduce(operator.mul, xrange(1,n+1))
... 
>>> fact2(5)
120

To my surprise, this actually resulted in slower performance. Here's the Q&D benchmarks:

>>> def fact(n): return (lambda x,y: x*y, range(1,n+1))
... 
>>> t1 = Timer("fact(500)", "from __main__ import fact")
>>> print t1.timeit(number = 500)
0.00656795501709

>>> def fact2(n): return reduce(operator.mul, xrange(1,n+1))
...
>>> t2 = Timer("fact2(500)", "from __main__ import fact2")
>>> print t2.timeit(number = 500)
0.35856294632

>>> def fact3(n): return reduce(operator.mul, range(1,n+1))
... 
>>> t3 = Timer("fact3(500)", "from __main__ import fact3")
>>> print t3.timeit(number = 500)
0.354646205902

>>> def fact4(n): return reduce(lambda x,y: x*y, xrange(1,n+1))
... 
>>> t4 = Timer("fact4(500)", "from __main__ import fact4")
>>> print t4.timeit(number = 500)
0.479015111923

>>> def fact5(n):
...     x = 1
...     for i in range(1, n+1):
...             x *= i
...     return x
... 
>>> t5 = Timer("fact5(500)", "from __main__ import fact5")
>>> print t5.timeit(number = 500)
0.388549804688

Here's my Python version in case anyone wants to cross-check my results:

Python 2.6.2 (release26-maint, Apr 19 2009, 01:56:41) 
[GCC 4.3.3] on linux2

Answer 4

A correct implementation of fact (returning 1 for fact(0)) is as follow:

def fact(n): return reduce(operator.mul, xrange(2,n+1), 1)

This is slightly faster (1.18 time faster) than the more readable

def fact1(n):
    x = 1
    for i in xrange(2,n+1):
        x*=i
    return x

P.S: the one can be skipped in both iterations because multiplying by one does not change the value

P.P.S: After timing, math.factorial seems slower than reduce:

>>> t1 = Timer("factorial(1000)", "from math import factorial")
>>> t1.timeit(number=1000)
0.8635700906120749
>>> def fact(n): return reduce(operator.mul, xrange(2,n+1), 1)
>>> t2 = Timer("fact(1000)", 'from __main__ import fact')
>>> t2.timeit(number=1000)
0.78937295103149552

The tests were done with python 2.6.2 on win32.

But I agree that the speed-up is probably not sufficient to justify writing your own factorial and math.factorial do some error checking (input must be a non negative integer)

Answer 5

I understand that you are probably trying to implement this yourself for educational reasons.

However, if not, I recommend using the math modules built-in factorial function (note: requires python 2.6 or higher):

>>> import math
>>> math.factorial(5)
120

This module is written in C, and as such, it'll be much much faster than writing it in python. (although, if you aren't computing large factorials, it won't really be too slow either way).

Answer 6

The reason Mark Rushakoff's fact(n) function was so much more efficient was that he missed-off the reduce() function. Thus it never actually did the calculation.

Corrected it reads (and I get):

import operator, timeit, math
#
def fact1(n):  return reduce(lambda x,y: x*y,  range(1,n+1),1)
def fact1x(n): return reduce(lambda x,y: x*y, xrange(1,n+1),1)
def fact2(n):  return reduce(operator.mul   ,  range(1,n+1),1)
def fact2x(n): return reduce(operator.mul   , xrange(1,n+1),1)
#
def factorialtimer():
    for myfunc in [ "fact1", "fact1x", "fact2", "fact2x" ]:
        mytimer = timeit.Timer(myfunc+"(1500)", "from __main__ import "+myfunc)
        print("{0:15} : {1:2.6f}".format(myfunc, mytimer.timeit(number=1000)))

    mytimer = timeit.Timer("factorial(1500)", "from math import factorial")
    print("{0:15} : {1:2.6f}".format("math.factorial", mytimer.timeit(number=1000)))

Resulting output for 1500!, 1000x:

fact1           : 3.537624
fact1x          : 4.448408
fact2           : 4.390820
fact2x          : 4.333070
math.factorial  : 4.091470

And yes, I have checked they all yield the same value! I Can't understand why the lambda xrange is so much worse than the lambda range. Hmmm. Version: PythonWin 2.6.2 (r262:71605, Apr 14 2009, 22:40:02) [MSC v.1500 32 bit (Intel)] on win32.

Hmm... on re-running it I get something more believable

fact1           : 7.771696
fact1x          : 7.799568
fact2           : 7.056820
fact2x          : 7.247851
math.factorial  : 6.875827

And on Python 2.6.5 (r265:79063, Jun 12 2010, 17:07:01) [GCC 4.3.4 20090804 (release) 1] on cygwin:

fact1           : 6.547000
fact1x          : 6.411000
fact2           : 6.068000
fact2x          : 6.246000
math.factorial  : 6.276000

All in the noise really, isn't it?