问题描述
我正在努力改善大数的因子计算的运行时间。
第一个简单循环和乘法的代码。
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 s。
从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.
所以我厌倦了删除尾随零然后相乘。
没有尾随零代码。
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
1楼
没有尾随零似乎不是很有效。
首先，我建议使用来减少乘法的总数，因为小于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
（PS。在你的第一个程序中，对于n = 100000，我机器的总时间是3.454秒。）
现在让我们测试它是否有效而没有尾随零。
尾随零的数量等于n!中素数因子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
它比以前快一点。 所以没有尾随零似乎不是很有用
2楼
我不知道这是否可以解决您的问题，但您可以尝试这种方法：
我看到你的要求是10 ^ 4（最大）的阶乘。 所以，
- 创建一个筛子，找到高达10000的所有素数。
- 现在，将所有数字从1分解为10000，并将其存储在数组中。 （这两个步骤不应该花费太多时间）。
- 所以，你现在将拥有1229个素数和他们的权力。
- 获得所有素数的幂并将它们全部乘以。 对于长数字，这会将乘法运算的数量从10000减少到1229.（但同时，需要一些时间才能找到功率。）
PS :(我不是很熟悉w / python，否则我自己做过）