有效地计算阶乘而不尾随零？
我试图改进大数的阶乘计算的运行时间。
第一个简单循环和乘法的代码。
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 s
for n=10000--总时间：0.035327 s
对于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 s
for n=10000--总时间：0.023636 s
对于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
此函数的分析结果：
for n=1000--总时间：0.061524 s
对于n=10000——总时间：113.824 s
因此，不是减少时间，而是增加时间，因为字符串转换也有“96.2%”的时间花在这上面
22 500 59173 118.3 96.2 shift = len(str(factorial)) - len(str(factorial).rstrip('0')).
所以我的问题是如何在不影响时间的情况下有效地使用尾随的零和移位。
所有分析都在上完成。基本操作系统（Linux）：64位，内存：6GB
共有2个答案
我不知道这是否能解决你的问题，但你可以试试这种方法：
我看到你的要求是10^4（最大）的阶乘。所以，
- 创建一个筛子，找到所有小于等于10000的素数
PS：（我不是很熟悉w/python，否则我会自己做）
没有尾随零似乎效率不高。
首先，我建议使用素数分解来减少乘法总数，因为小于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。）
现在，让我们测试它是否在没有尾随零的情况下有效。尾随零的个数等于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
只是比以前快了一点。因此，没有尾随零似乎不是很有用
-
问题内容： 我正在尝试计算阶乘产生的数字的尾随零（这意味着数字变得很大）。以下代码采用一个数字，计算该数字的阶乘，并计算尾随零。但是，当数字大约为25！时，numZeros将不起作用。 我并不担心这段代码的效率，并且我知道有多种方法可以使这段代码的效率更好。我要弄清楚的是为什么计数大于25的数字结尾的零！不管用。 有任何想法吗？ 问题答案： 您的任务不是计算阶乘，而是计算零的数量。一个好的解决方案
-
我试图计算阶乘中尾随零的数量。 我认为尾随零的数量不正确。 使用计数（30）时，30中有7个尾随的0。然而，它正在返回6。
-
当我提交给leetcode时，它运行案例500/502，但失败了，原因是：1808548329。但当我在自己的mac上运行它时，它给出了与公认的答案相同的答案。 我的代码： 交流答案是： 它们在我的mac上运行相同的结果： 第一个解决方案之所以不被接受，是因为时间复杂度 （因为我在自己的mac上运行它，但它给出了与ac相同的答案） 如何计算第一个解决方案的时间复杂度， 它是O（NlogN）吗？我不
-
我是C编程新手，我想找出给定数的阶乘中尾随零的数量 我尝试计算数字的模，它将返回给定数字的最后一位作为余数，然后将删除最后一个数字。 执行程序后，输出总是将尾随零的数量显示为“0”，如果（ln=！0）条件始终得到满足，即使存在零。
-
我试图计算给定数字的阶乘中尾随零的数量，例如。， ，其中尾随零 ，其中尾随零 我的问题是，我有一个像df这样的数据帧 我知道R中的阶乘是用来计算阶乘的，但我不知道如何计算尾部的零。任何帮助都将不胜感激！
-
我如何使程序执行一个新的或重复的操作，或要求用户再次输入一个数字，并知道它的阶乘。