Function for Factorial in Python

How to make my factorial function faster and efficient?

Because of the maximum recursion depth, you will not be able to compute factorials greater than 1000 (actually smaller because some stack levels are already used by other calling functions)

So you need to implement an iterative approach. To produce numbers expressed as digits in a list, it will be easier to store the digits in reverse order so that the index of a digit corresponds to the power of 10 it is multiplied by. You can reverse the list for human readability when printing or when returning the result.

With this digit storage strategy the multiplication logic can be more straightforward. You should also implemented it without "cheating" with Python's infinite size integers (e.g. 10**((len(listx)-n-1)+(len(listy)-m-1)):

def toDigits(n):
    result = []
    while n:
        n,d = divmod(n,10)
        result.append(d)
    return result or [0]

def multDigits(A,B):
    result = [0]
    for i,a in enumerate(A):
        for j,b in enumerate(B):
            p10,carry = i+j,a*b 
            while carry:
                if p10 >= len(result): result.append(0); continue
                carry,result[p10] = divmod(carry+result[p10],10)
                p10 += 1
    return result

def factorial(N):
    result = [1]
    for n in range(2,N+1):
        result = multDigits(result,toDigits(n))
    return result[::-1]

output:

print(factorial(1000))

[4, 0, 2, 3, 8, 7, 2, 6, 0, 0, 7, 7, 0, 9, 3, 7, 7, 3, 5, ...

# proof that it works:

from math import factorial
digits = [ int(d) for d in str(factorial(1000)) ]
print(digits)

[4, 0, 2, 3, 8, 7, 2, 6, 0, 0, 7, 7, 0, 9, 3, 7, 7, 3, 5, ...

Recursion in Python (factorial function)

n == 0 is the base case of the recursive function. Factorial of 0 is 1: reference

Once the base case returns 1, the statement return n * factorial(n-1) will have the form: return n * 1 and so on.

matplotlib and the factorial function

There are 2 things about your code:

1. I think math functions only accept scalars (int, float, etc), not list or numpy array.

2. The factorial function is defined for (positive) integers only, not for float, e.g. 0.5.

I think you are looking for the gamma function, which extends the factorial function over the real numbers:

from scipy.special import gamma

x = np.linspace(0, 10, 1000)
plt.plot(x,gamma(x), label='Factorial')
plt.plot(x, x**5, label='$x^5$')

xx = np.arange(11)
plt.scatter(xx, gamma(xx))
plt.legend()

Output:

Python: Using def in a factorial program

Not entirely sure what you are asking. As I understand your question, you want to refactor your script so that the calculation of the factorial is a function. If so, just try this:

def factorial(x):             # define factorial as a function
    f = 1
    for n in range(2, x + 1):
        f = f * n
    return f

def main():                   # define another function for user input
    x = int(input("Please enter a number greater than or equal to 0: "))
    f = factorial(x)          # call your factorial function
    print(x,'factorial is',f)

if __name__ == "__main__":    # not executed when imported in another script
    main()                    # call your main function

This will define a factorial function and a main function. The if block at the bottom will execute the main function, but only if the script is interpreted directly:

~> python3 test.py 
Please enter a number greater than or equal to 0: 4
4 factorial is 24

Alternatively, you can import your script into another script or an interactive session. This way it will not execute the main function, but you can call both functions as you like.

~> python3
>>> import test
>>> test.factorial(4)
24

---

Related Topics