464,397 Members | 1,110 Online Need help? Post your question and get tips & solutions from a community of 464,397 IT Pros & Developers. It's quick & easy.

# Increase performance for finding Factorial of large numbers

 P: 2 I am using iterative method and recursion method to implement factorial but when finding the same for large numbers,it takes alot of time.Any way to change that? Sep 1 '20 #1

I get your question , the problem of computing factorial has a highly repetitive structure. You can use dynamic programming to solve your problem. The conditions for implementing dynamic programming are
• Overlapping sub-problems
• optimal substructure

Here is a code which may help you to understand what I am trying to say
Expand|Select|Wrap|Line Numbers
1. def DPfact(N):
2.     arr={}
3.     if N in arr:
4.         return arr[N]
5.     elif N == 0 or N == 1:
6.         return 1
7.         arr[N] = 1
8.     else:
9.         factorial = N*DPfact(N - 1)
10.         arr[N] = factorial
11.     return factorial
12.
13. num=int(input("Enter the number: "))
14.
15. print("factorial of ",num," (dynamic): ",end="")
16. print(DPfact(num))
To get a more clear idea on factorial from basics to such advance level,

4 Replies

 P: 13 I get your question , the problem of computing factorial has a highly repetitive structure. You can use dynamic programming to solve your problem. The conditions for implementing dynamic programming are Overlapping sub-problems optimal substructure Here is a code which may help you to understand what I am trying to say Expand|Select|Wrap|Line Numbers def DPfact(N):     arr={}     if N in arr:         return arr[N]     elif N == 0 or N == 1:         return 1         arr[N] = 1     else:         factorial = N*DPfact(N - 1)         arr[N] = factorial     return factorial   num=int(input("Enter the number: "))   print("factorial of ",num," (dynamic): ",end="") print(DPfact(num)) To get a more clear idea on factorial from basics to such advance level, Sep 1 '20 #2

 P: 2 Thankyou, It kinda helped Sep 1 '20 #3

 100+ P: 200 The math module factorial implemented in C is faster than the recursive call. Expand|Select|Wrap|Line Numbers import math num=int(input("Enter the number: ")) print(math.factorial(num)) Sep 2 '20 #4

 Expert 100+ P: 335 Here's the inbuilt factorial algorithm in case anyone's interested https://hg.python.org/cpython/file/7...module.c#l1218 Sep 6 '20 #5 