我正在努力提高大数阶乘计算的运行时间。
第一个简单循环和乘法的代码。
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
此函数的分析结果：
n＝1000 -总时间：0.001115秒
对于n＝10000——总时间：0.035327秒
n＝100000 -总时间：3.77454秒。
对于N = 100000的行分析器，我可以看到大部分的%时间都用在乘法步骤中，即“98.8”。
31 100000 3728380 37.3 98.8 result *= x
所以尽量减少阶乘
一半，偶数，因此做强度降低。
下半乘法码：
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
此函数的分析结果：
n＝1000 -总时间：0.00115秒
n＝10000 -总时间：0.023636秒
对于n＝100000——总时间：3.65019秒
这表明在中等范围内有所改善，但在缩放方面没有太大改善。
在这个函数中，%的大部分时间花在乘法运算上。
61 50000 3571928 71.4 97.9 factorial *= next_multi.
所以我想去掉后面的0，然后再乘。
没有尾随零代码。
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
此函数的分析结果：
n＝1000 -总时间：0.061524秒
n＝10000 -总时间：113.824秒
因此，不是减少时间，而是因为字符串转换而增加时间，因为时间的“96.2%”也花费在那个时间上。
22 500 59173 118.3 96.2 shift = len(str(factorial)) - len(str(factorial).rstrip('0')).
所以我的问题是如何得到后继零点，并有效地使用移位而不损害时间。
所有分析都在上完成。
基本操作系统（Linux）：64位，RAM:6GB
最佳答案
没有尾随零似乎不是很有效。
首先，我建议使用prime decomposition来减少乘法的总数，因为小于x的素数约为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
n=10000，总时间：0.017s
n=100000，总时间：2.047s
n=500000，总时间：65.324s
（注意，在您的第一个程序中，如果n=100000，则在我的机器中的总时间为3.454s。）
现在让我们测试一下它是否在没有尾随零的情况下有效。尾随零的个数等于
5中素数因子n!的个数。程序是这样的
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)
n=10000，总时间：0.015s
n=100000，总时间：1.896s
n=500000，总时间：57.101s
只是比以前快了一点。所以没有尾随的零看起来不是很有用