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

Solution 1:

The line that your error is on should read

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

Solution 2:

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

Solution 3:

Here's your code, fixed up and working:

import sys
number = int(sys.argv[1])
fact = 1for 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.

Solution 4:

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
#deffact1(n):  return reduce(lambda x,y: x*y,  range(1,n+1),1)
deffact1x(n): return reduce(lambda x,y: x*y, xrange(1,n+1),1)
deffact2(n):  return reduce(operator.mul   ,  range(1,n+1),1)
deffact2x(n): return reduce(operator.mul   , xrange(1,n+1),1)
#deffactorialtimer():
    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.537624fact1x          :4.448408fact2           :4.390820fact2x          :4.333070math.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.771696fact1x          :7.799568fact2           :7.056820fact2x          :7.247851math.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.547000fact1x          :6.411000fact2           :6.068000fact2x          :6.246000math.factorial  :6.276000

All in the noise really, isn't it?

Solution 5:

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

>>>deffact(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>>>deffact2(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:

>>>deffact(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

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

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

>>>deffact4(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

>>>deffact5(n):...    x = 1...for i inrange(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 192009, 01:56:41) 
[GCC 4.3.3] on linux2

howtostartbloggingformoney