I have been trying to work it out for a long time now. Many of the programming challenges involve frequent us of factorials which contribute to the solution of the problem. Needless to say, the value gets large fairly quickly, and gets difficult to calculate in small time slice too.
So can any of you explain to me an efficient way of finding factorials. It would be of great help!
Thanks in advance,
Osman 
Hello Osman!!
If you refer to the computation of a factorial in mathematical versus computer programming terms, the best way to do it is maintain a running product, i.e., do it iteratively:
FUNCTION fact(N):
ans = 1
for i = 1 to N
ans = ans*i
return ans
The above idea is to be applied even if the factorial is huge… The difference is that the digits should be kept in an array and grade-school multiplication using carry to maintain the numbers small will be necessary…
//using recursivity
#include
using namespace std;
long fac(long i)
{
if (i==0)
{
return (1);
}
else
{return (i*fac(i-1));}
}
int main()
{
int z;
cout<<“enter number”;
cin>>z;
cout<<z<<"!="<< fac (z);
return 0;
}
hello Osman
:
i am new on codechef
you can code for factorial but for efficiency--------
1)if you go with recursion-it takes more memory coz it will use stack
2)if you go with for loop it takes more time
3)with the while loop it will be more efficient in both ways memory and time
Your 3rd point is absurd. while loop is no more efficient than for loop.
Not really the best way, especially if you need many different factorials (you should build a table). If you’ll only need one factorial then this is probably okay (hopefully it is simple enough for the compiler to elide the function calls away) but writing the multiplies in a loop isn’t much harder.
Most of the time when you need factorials, you’ll need many of them, so the best idea is to build a table. Then you can compute each one in constant time on average by using n! = n*(n-1)!.
Usually you’ll be doing the computations modulo something so the values don’t grow exponentially large, if not then doing big integer multiplications will start to slow you down so beware. In that case maybe look into Chinese Remainder Theorem since using it you can avoid having large numbers until the very end.
If you have to cover a really big range, it may work to find all primes up to your modulus, and then determine how many of each appears in your factorial. If you haven’t seen that before, the maximum power e s.t. prime power p^e divides n! is given by e = floor(n/p) + floor(floor(n/p)/p) + floor(floor(floor(n/p)/p)/p)... which is easy to calculate in an O(log n) loop. Note that you can save some work here by calculating the first prime where e = 1 (or even the first prime where e <= 2) and not bothering to step past that. Once you have those powers, you can use modular exponentiation to efficiently raise them, then multiply them all together. It’s tough to say if this will be significantly faster than just multiplying or not, but perhaps there is some preprocessing that can be done to accelerate it.
Other than that, maybe precalculating say every 1000th value and then filling in gaps at runtime would be a good plan. If the modulus is small (or has small factors) then it helps because every factorial starting at m! is divisible by m. Occasionally Wilson’s Theorem ( (p-1)! == -1 mod p iff p is prime) may be useful (but I don’t have an example where it is).
I have detailed a method to halve the multiplication required here. I would recommend using the first method, but the second method an interesting read is you understand it. I would also recommend storing a cache of prime numbers that you have calculated. If there is no prime numbers close to a solved prime number in your cache, then calculate it with the first method, otherwise multiply or divide the closest prime number to calculate the prime you need, and every prime between the two efficiently.
how any of the loop will produce a good result in respect to memory and time ??
@vinod10101989 one thing i would say u that a if a problem is solvable by recursion as well as looping go with looping because it is apperently faster than recursion the reason behind this is in case of recursion frequent function calling takes place resulting in frequent control transfer…which takes more time…also ur concept about different looping statements (for,while,do-while) are wrong .they are same w.r.t running time.
use python or java if you know it…coz they have built in libraries which can store a value upto 15 digits…and thus python can help you to find the fact in a quick time with a simple algorithm that is taught to us in 11 and 12 class in the school
One simple optimization is the strategy of multiplication . If you want to calculate 123456789 * 456 , instead of calculating by writing an 2D array and then adding all of them , we can do that by considering 456 as a single digit like this . 456 * 9 is 4104 , so put 4 in the units place of the result and take 410 as the carry for next multiplication , then 456 * 8 is 3648 , and by adding the previous carry of 410 we get 4058 , so put 8 in the tens place and take 405 as carry and continue ahead , till all the digits have been completed .
as if recursion will take less time?
for loop takes more,why because it is entry controlled loop?
3rd point,my god it answers the above 2 questons…
Some people have mentioned it already. When it comes to problems involving factorials, it’s best to precompute and store the values in a table. A typical problem may also require you to perform a modulo operation to avoid integer overflow. So you’ll probably wind up with something like:
long long factorials[N+1];
init_factorials()
{
factorials[0] = factorials[1] = 1;
for i = 2...N
{
factorials[i] = (i * factorials[i-1]) % MOD;
}
}