By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
464,397 Members | 1,110 Online
Bytes IT Community
+ Ask a Question
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

✓ answered by hussainmujtaba

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,

Share this Question
Share on Google+
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
  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,
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
  1. import math
  2. num=int(input("Enter the number: "))
  3. print(math.factorial(num))
Sep 2 '20 #4

dev7060
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

Post your reply

Sign in to post your reply or Sign up for a free account.