fastest algorithm for factorial

general
, ,
1

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)
2

from math import factorial

3

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
4

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

5

link text

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

1 Like
6

i wanted it for ‘factorial’ question in easy section

7

What do you want?

8

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

9

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: performance - Why is math.factorial much slower in Python 2.x than 3.x? - Stack Overflow

10

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

1 Like
11

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!