Calculating The Factorial Without Trailing Zeros Efficiently?

I'm trying to improve the running time of the factorial calculation of the large number. The first Code which simply loop over and multiplies. def calculate_factorial_multi(number)

Solution 1:

Without trailing zero seems not very efficient.

First, I suggested using prime decomposition to reduct total number of multiplications because prime numbers smaller than x is about x/lnx.

def calculate_factorial_multi(number):
    prime = [True]*(number + 1)
    result = 1
    for i in xrange (2, number+1):
        if prime[i]:
            #update prime table
            j = i+i
            while j <= number:
                prime[j] = False
                j += i
            #calculate number of i in n!
            sum = 0
            t = i
            while t <= number:
                sum += number/t
                t *= i
            result *= i**sum
    return result

for n = 10000, total time : 0.017s

for n = 100000, total time : 2.047s

for n = 500000, total time : 65.324s

(PS. in your first program, for n = 100000, total time is 3.454s in my machine.)

Now let's test whether it is efficient without trailing zero. The number of trailing zero equals the number of prime factors 5 in n!. The program is like this

def calculate_factorial_multi2(number):
    prime = [True]*(number + 1)
    result = 1
    factor2 = 0
    factor5 = 0
    for i in xrange (2, number+1):
        if prime[i]:
            #update prime table
            j = i+i
            while j <= number:
                prime[j] = False
                j += i
            #calculate the number of i in factors of n!
            sum = 0
            t = i
            while t <= number:
                sum += number/t
                t *= i
            if i == 2:
                factor2 = sum
            elif i == 5:
                factor5 = sum
            else:
                result *= i**sum

    return (result << (factor2 - factor5))*(10**factor5)

for n = 10000, total time : 0.015s

for n = 100000, total time : 1.896s

for n = 500000, total time : 57.101s

It is just a little faster than before. So Without trailing zero seems not very useful

Solution 2:

I don't exactly know if this would solve your problem, but you can try this method:

I see that your requirement is factorial of 10^4 (max). So,

• Create a sieve and find all prime numbers up to 10000.
• Now, prime factorize all numbers from 1 to 10000, and store it in array. (These two steps should not take much time).
• So, you will now be having exactly 1229 primes and their powers.
• Get the powers of all primes and multiply them all. For long numbers, that will reduce number of multiply operations from 10000 to 1229. (But, at the same time it will take some time to find the powers.)

PS: (I'm not very familiar w/ python or else I'd have done it myself)