# fastest algorithm for factorial

**URL:** <https://discuss.codechef.com/t/fastest-algorithm-for-factorial/3469>\
**Category:** general\
**Tags:** factorial, python, recursion\
**Created:** [October 19, 2013, 10:52am UTC](https://discuss.codechef.com/t/fastest-algorithm-for-factorial/3469 "2013-10-19T10:52:36Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![singhiskng](https://discuss.codechef.com/user_avatar/discuss.codechef.com/singhiskng/32/120757_2.png) [@singhiskng](https://discuss.codechef.com/u/singhiskng)\
**Post date:** [October 19, 2013, 10:52am UTC](https://discuss.codechef.com/t/fastest-algorithm-for-factorial/3469/1 "2013-10-19T10:52:36Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![xylon97](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@xylon97](https://discuss.codechef.com/u/xylon97)\
**Post date:** [October 19, 2013, 12:40pm UTC](https://discuss.codechef.com/t/fastest-algorithm-for-factorial/3469/2 "2013-10-19T12:40:44Z")

</div>

from math import factorial

---

<div class="post-metadata">

**Author:** ![kcahdog](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@kcahdog](https://discuss.codechef.com/u/kcahdog)\
**Post date:** [October 19, 2013, 12:51pm UTC](https://discuss.codechef.com/t/fastest-algorithm-for-factorial/3469/3 "2013-10-19T12:51:14Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![singhiskng](https://discuss.codechef.com/user_avatar/discuss.codechef.com/singhiskng/32/120757_2.png) [@singhiskng](https://discuss.codechef.com/u/singhiskng)\
**Post date:** [October 19, 2013, 1:45pm UTC](https://discuss.codechef.com/t/fastest-algorithm-for-factorial/3469/4 "2013-10-19T13:45:05Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![bipin2](https://discuss.codechef.com/user_avatar/discuss.codechef.com/bipin2/32/7810_2.png) [@bipin2](https://discuss.codechef.com/u/bipin2)\
**Post date:** [October 19, 2013, 4:25pm UTC](https://discuss.codechef.com/t/fastest-algorithm-for-factorial/3469/5 "2013-10-19T16:25:52Z")

</div>

[link text](http://ideone.com/KW2Ons)

check for this one  
for more help lokk in this tutorial here [link text](http://blog.codechef.com/2009/07/02/tutorial-for-small-factorials/)

---

<div class="post-metadata">

**Author:** ![singhiskng](https://discuss.codechef.com/user_avatar/discuss.codechef.com/singhiskng/32/120757_2.png) [@singhiskng](https://discuss.codechef.com/u/singhiskng)\
**Post date:** [October 19, 2013, 1:42pm UTC](https://discuss.codechef.com/t/fastest-algorithm-for-factorial/3469/6 "2013-10-19T13:42:16Z")

</div>

i wanted it for ‘factorial’ question in easy section

---

<div class="post-metadata">

**Author:** ![kcahdog](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@kcahdog](https://discuss.codechef.com/u/kcahdog)\
**Post date:** [October 19, 2013, 2:17pm UTC](https://discuss.codechef.com/t/fastest-algorithm-for-factorial/3469/7 "2013-10-19T14:17:11Z")

</div>

What do you want?

---

<div class="post-metadata">

**Author:** ![singhiskng](https://discuss.codechef.com/user_avatar/discuss.codechef.com/singhiskng/32/120757_2.png) [@singhiskng](https://discuss.codechef.com/u/singhiskng)\
**Post date:** [October 19, 2013, 5:44pm UTC](https://discuss.codechef.com/t/fastest-algorithm-for-factorial/3469/8 "2013-10-19T17:44:47Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![ankurparihar](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ankurparihar/32/83191_2.png) [@ankurparihar](https://discuss.codechef.com/u/ankurparihar)\
**Post date:** [October 23, 2019, 4:01am UTC](https://discuss.codechef.com/t/fastest-algorithm-for-factorial/3469/9 "2019-10-23T04:01:41Z")

</div>

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](https://stackoverflow.com/questions/9815252/why-is-math-factorial-much-slower-in-python-2-x-than-3-x)

---

<div class="post-metadata">

**Author:** ![anon70990627](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon70990627](https://discuss.codechef.com/u/anon70990627)\
**Post date:** [October 23, 2019, 8:17am UTC](https://discuss.codechef.com/t/fastest-algorithm-for-factorial/3469/10 "2019-10-23T08:17:28Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![tl0n](https://discuss.codechef.com/user_avatar/discuss.codechef.com/tl0n/32/10519_2.png) [@tl0n](https://discuss.codechef.com/u/tl0n)\
**Post date:** [February 6, 2020, 5:19am UTC](https://discuss.codechef.com/t/fastest-algorithm-for-factorial/3469/11 "2020-02-06T05:19:30Z")

</div>

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.

```cpp
#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!