在没有尾随零的情况下有效地计算阶乘？

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

此功能的配置结果:

对于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

Answer 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秒.)

现在让我们测试它是否有效而没有尾随零.尾随零的数量等于素数因子的数量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

它比以前快一点.所以没有尾随零似乎不是很有用