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):
'''
This function takes one agruments and
returns the factorials of that number
This function uses the approach successive multiplication
like 8! = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
'''
'''
If 0 or 1 retrun immediately
'''
if number == 1 or number == 0:
return 1
result = 1 # variable to hold the result
for x in xrange(1, number + 1, 1):
result *= x
return result
The profiled result for this function :
For n = 1000 -- Total time: 0.001115 s
for n = 10000 -- Total time: 0.035327 s
for n = 100000 -- Total time: 3.77454 s.
From the line profiler for n = 100000 i can see that most of the %time was spent in multiplication step which is '98.8'
31 100000 3728380 37.3 98.8 result *= x
So tried to reduce the multiplication in factorial by half, for even number, hence doing Strength Reduction.
Second half multiplication Code:
def calculate_factorial_multi_half(number):
if number == 1 or number == 0:
return 1
handle_odd = False
upto_number = number
if number & 1 == 1:
upto_number -= 1
print upto_number
handle_odd = True
next_sum = upto_number
next_multi = upto_number
factorial = 1
while next_sum >= 2:
factorial *= next_multi
next_sum -= 2
next_multi += next_sum
if handle_odd:
factorial *= number
return factorial
The profiled result for this function :
For n = 1000 -- Total time: 0.00115 s
for n = 10000 -- Total time: 0.023636 s
for n = 100000 -- Total time: 3.65019 s
Which shows some improvement in the mid range but didn't improved much with scaling.
In this function too most of the %time is spent on multiplication.
61 50000 3571928 71.4 97.9 factorial *= next_multi.
So I tired to remove the trailing zeros and then multiply.
Without Trailing zeros code.
def calculate_factorial_multi_half_trailO(number):
'''
Removes the trailling zeros
'''
if number == 1 or number == 0:
return 1
handle_odd = False
upto_number = number
if number & 1 == 1:
upto_number -= 1
handle_odd = True
next_sum = upto_number
next_multi = upto_number
factorial = 1
total_shift = 0
while next_sum >= 2:
factorial *= next_multi
shift = len(str(factorial)) - len(str(factorial).rstrip('0'))
total_shift += shift
factorial >>= shift
next_sum -= 2
next_multi += next_sum
if handle_odd:
factorial *= number
factorial <<= total_shift
return factorial
The profiled result for this function :
For n = 1000 -- Total time: 0.061524 s
for n = 10000 -- Total time: 113.824 s
so instead of decreasing the time it's increasing the time because of the string conversion as also '96.2%' of the time is spend on that
22 500 59173 118.3 96.2 shift = len(str(factorial)) - len(str(factorial).rstrip('0')).
So my question is how can i get the trailing zeros and use with shift efficiently without compromising the time.
All the profiling done on. Elementary OS(Linux): 64bit, Ram : 6GB
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