有效地计算无尾随零的阶乘？

Question

我试图改进大数的阶乘计算的运行时间。在

第一个简单地循环和倍增的代码。在

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

此函数的分析结果：

For n = 1000 -- Total time: 0.001115 s

for n = 10000 -- Total time: 0.035327 s

for n = 100000 -- Total time: 3.77454 s.

从n=100000的测线仪可以看出，大部分%的时间都花在乘法步骤上，即'98.8'

^{pr2}$

所以尽量减少阶乘 减半，为偶数，因此做强度减少。在

后半乘法码：

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

此函数的分析结果：

For n = 1000 -- Total time: 0.00115 s

for n = 10000 -- Total time: 0.023636 s

for n = 100000 -- Total time: 3.65019 s

这表明在中等范围内有一些改进，但在缩放后没有太大改善。在

在这个函数中，大部分%的时间都花在乘法上。在

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

此函数的分析结果：

For n = 1000 -- Total time: 0.061524 s

for n = 10000 -- Total time: 113.824 s

因此，不是减少时间而是增加时间，因为字符串转换也花费了96.2%的时间

 22       500        59173    118.3     96.2        shift = len(str(factorial)) - len(str(factorial).rstrip('0')).

所以我的问题是，如何在不影响时间的情况下，有效地获取尾随的0并使用with shift。在

所有的分析都在上面完成。 基本操作系统（Linux）：64位，Ram:6GB

Answer 1

没有尾随零似乎不是很有效。

首先，我建议使用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

for n = 10000, total time : 0.017s

for n = 100000, total time : 2.047s

for n = 500000, total time : 65.324s

（注：在您的第一个程序中，对于n=100000，在我的机器中总时间是3.454s。）

现在让我们来测试它是否有效，而不需要尾随零。尾随零的数目等于n!中的素因子5的数目。 程序是这样的

^{pr2}$

for n = 10000, total time : 0.015s

for n = 100000, total time : 1.896s

for n = 500000, total time : 57.101s

只是比以前快了一点。所以没有尾随零似乎不是很有用

Answer 2

我不知道这是否能解决你的问题，但你可以试试这个方法：

我知道你的要求是10^4的阶乘。所以

• 创建一个筛子，找出所有小于等于10000的质数。在
• 现在，对1到10000之间的所有数字进行素数因式分解，并将其存储在数组中。（这两个步骤不需要太多时间）。在
• 所以，你现在有1229个质数和它们的能量。在
• 求出所有素数的幂，然后将它们全部相乘。对于长数，这将把乘法运算的数量从10000减少到1229。（但是，同时还需要一段时间才能找到力量。）

PS：（我对python不太熟悉，否则我会自己做的）