CODEWITHSUNDEEP
pythonfactorial
codeimplementer
codeimplementer

Reputation: 3383

find the best way for factorial in python?

I am researching on speed of factorial. But I am using two ways only,

import timeit

def fact(N):
    B = N
    while N > 1:
        B = B * (N-1)
        N = N-1
    return B

def fact1(N):
    B = 1
    for i in range(1, N+1):
        B = B * i
    return B


print timeit.timeit('fact(5)', setup="from __main__ import fact"), fact(5)
print timeit.timeit('fact1(5)', setup="from __main__ import fact1"), fact1(5)

Here is the output,

0.540276050568 120
0.654400110245 120

From above code I have observed,

  1. While take less time than for

My question is,

Is the best way to find the factorial in python ?

Upvotes: 3

Views: 2968

Answers (4)

Nilesh
Nilesh

Reputation: 2555

I have tried with reduce(lambda x, y: x*y, range(1, 5))

>>>timeit("import math; math.factorial(4)")
1.0205099133840179

>>>timeit("reduce(lambda x, y: x*y, range(1, 5))")
1.4047879075160665

>>>timeit("from operator import mul;reduce(mul, range(1, 5))")
2.530837320051319

Upvotes: 0

James Mills
James Mills

Reputation: 19030

Otherwise, if you're looking for a Python implementation (this is my favourite):

from operator import mul


def factorial(n):
    return reduce(mul, range(1, (n + 1)), 1)

Usage:

>>> factorial(0)
1
>>> factorial(1)
1
>>> factorial(2)
2
>>> factorial(3)
6
>>> factorial(4)
24
>>> factorial(5)
120
>>> factorial(10)
3628800

Performance: (On my desktop:)

$ python -m timeit -c -s "fact = lambda n: reduce(lambda a, x: a * x, range(1, (n + 1)), 1)" "fact(10)"
1000000 loops, best of 3: 1.98 usec per loop

Upvotes: 1

John La Rooy
John La Rooy

Reputation: 304195

TLDR; microbenchmarks aren't very useful

For Cpython, try this:

>>> from math import factorial


>>> print timeit.timeit('fact(5)', setup="from __main__ import fact"), fact(5)
1.38128209114 120
>>> print timeit.timeit('fact1(5)', setup="from __main__ import fact1"), fact1(5)
1.46199703217 120
>>> print timeit.timeit('factorial(5)', setup="from math import factorial"), factorial(5)
0.397044181824 120

But under pypy, the while is faster than the one from math

>>>> print timeit.timeit('fact(5)', setup="from __main__ import fact"), fact(5)\
0.170556783676 120
>>>> print timeit.timeit('fact1(5)', setup="from __main__ import fact1"), fact1\
(5)
0.319650173187 120
>>>> print timeit.timeit('factorial(5)', setup="from math import factorial"), f\
actorial(5)
0.210616111755 120

So it depends on the implementation. Now try bigger numbers

>>>> print timeit.timeit('fact(50)', setup="from __main__ import fact"), fact(50)
7.71517109871 30414093201713378043612608166064768844377641568960512000000000000
>>>> print timeit.timeit('fact1(50)', setup="from __main__ import fact1"), fact1(50)
6.58060312271 30414093201713378043612608166064768844377641568960512000000000000
>>>> print timeit.timeit('factorial(50)', setup="from math import factorial"), factorial(50)
6.53072690964 30414093201713378043612608166064768844377641568960512000000000000

while is in last place, and the version using for is about the same as the one from the math module

Upvotes: 4

mgilson
mgilson

Reputation: 309929

If you're looking for the best, why not use the one provided in the math module?

>>> import math
>>> math.factorial
<built-in function factorial>
>>> math.factorial(10)
3628800

And a comparison of timings on my machine:

>>> print timeit.timeit('fact(5)', setup="from __main__ import fact"), fact(5)
0.840167045593 120
>>> print timeit.timeit('fact1(5)', setup="from __main__ import fact1"), fact1(5)
1.04350399971 120
>>> print timeit.timeit('factorial(5)', setup="from math import factorial")
0.149857997894

We see that the builtin is significantly better than either of the pure python variants you proposed.

Upvotes: 12

Related Questions