fastest algorithm for factorial

which is best way for calculating factorial of a number n of more than 5 digit.

loop method:

s=1
for i in range(1,n+1):
    s*=i

recursion method:

def fact(n):
    if n==1 or n==0:
        return 1
    else:
        return n*fact(n-1)

from math import factorial

The loop will definitely be faster as it avoids the overhead of the function calls i.e.use of stack to store calling functions that are waiting for recursion to terminate. Infact i have sometimes noticed that replacing a function by code in the main part speeds up program by almost 2-3 times. Best way to analyse this would be to submit both codes and see their relative performance for the "small factorials " question in easy section.

1 Like

i had tried
import math math.factorial(), but when i calculate it for 100000 and above it take more time in python

link text

check for this one
for more help lokk in this tutorial here link text

1 Like

i wanted it for ‘factorial’ question in easy section

What do you want?

best algorithm for ‘factorial’ question ,so that my code doesn’t exceed the given time

Python 2 is much slower because it uses basic factorial algorithm

Python3 uses highly efficient C code to compute factorial. It may be useful in many cases even if python itself is very slow.

Reference: https://stackoverflow.com/questions/9815252/why-is-math-factorial-much-slower-in-python-2-x-than-3-x

For c++, use multiprecision/boost library. This might help you- https://www.geeksforgeeks.org/factorial-large-number-using-boost-multiprecision-library/

1 Like

Even though my solution is marked as ‘Wrong Answer’ by reasons I cannot fathom; I want to share my code here, hoping someone find it useful.

#include <iostream>
#include <vector>

using std::vector;

const int iTotalFactorials = 100;

void fillFactorials(vector<std::string>& SmallFactorials)
{
    std::string strPreviosFactorial;

    SmallFactorials.push_back("1"); // 0! (Zero factorial)
    SmallFactorials.push_back("1"); // 1! (One factorial)
    SmallFactorials.push_back("2"); // 2! (Two factorial)

    std::string strNewFactorial = "";

    for(int i=3; i < iTotalFactorials; i++)
    {

        strNewFactorial = "";
        strPreviosFactorial = SmallFactorials[i - 1]; 
        int lenFactorial = strPreviosFactorial.size();

        int iCarry = 0;
        int intDigit = 0;

        int j = 0;

        while (j < lenFactorial)
        {
            char facDigit = (char)strPreviosFactorial[lenFactorial - 1 - j];

            intDigit = (facDigit-'0') * i + iCarry;

            iCarry = intDigit/10;
            
            strNewFactorial = std::to_string(intDigit%10) + strNewFactorial;
            
            j++;
        }
        
        if (iCarry>0)
            strNewFactorial = std::to_string(iCarry) + strNewFactorial;

        SmallFactorials.push_back(strNewFactorial);
    }

    SmallFactorials.push_back(strNewFactorial + "0");
    
}


int main()
{
    vector<std::string> arryFactorials;
    int t = 0;

    fillFactorials(arryFactorials);

    std::cin >> t;

    for (int i=0; i<t; i++)
    {
        int j=0;
        std::cin >> j;
        
        std::cout << arryFactorials[j] << std::endl;
    }

    return 0;
}

best!