Fast algorithms for computing the factorial

user_176646 0
Viewed 37765

I found this page describing a number of algorithms for computing the factorial. Unfortunately, the explanations are terse and I don't feel like sifting through line after line of source code to understand the basic principles behind the algorithms.

Can anybody point me to more detailed descriptions of these (or other fast) algorithms for computing the factorial?

Edit: This page describes the method of prime factorization, the technique common to all of the best-performing factorial algorithms. It also contains some nice example code in Python. The author links to a description of binary splitting and references an article in the Journal of Algorithms ("On the Complexity of Calculating Factorials") that looks promising, if I could only get my hands on it.

factorial algorithm performance
3 Answers

More than ten years later, I would like to provide a Python approach inspired in the fact that you're interested in multiply factorial(n) * n+1 and the base cases are 0 and 1 whose result is 1, then:

def fact_var(num):
    a, b, i = 1,2,2 # base cases and our i counter.
    while i < num: # if i is equal to num, we're done, last product will be at return.
        c = a * b # start to multiply and save in c.
        i+=1 # add 1 to i because we want to multiply next number with c (in the next iteration).
        a, b = c, i # update variables to the next iteration.
    return a * b if num > 1 else 1 # last product occurs here is num is greater than 1.

print(fact_var(100000))

For factorial of 100 000 it takes up to 5 seconds in my machine, I hope it serves for documentation and upcoming viewers!

Ps. Same idea is useful to compute fibonacci, which is a summation not a multiplication.

user_55080870
Related