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