计算阶乘而不有效尾随零? [英] Calculating the factorial without trailing zeros efficiently?

问题描述

我正在尝试提高大数阶乘计算的运行时间.

I'm trying to improve the running time of the factorial calculation of the large number.

第一个简单地循环并相乘的代码.

The first Code which simply loop over and multiplies.

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 = 1000 -- Total time: 0.001115 s

n = 10000-总时间:0.035327 s

for n = 10000 -- Total time: 0.035327 s

n = 100000-总时间:3.77454 s.

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

从n = 100000的行探查器中，我可以看到大部分％time花费在乘法步骤"98.8"上

From the line profiler for n = 100000 i can see that most of the %time was spent in multiplication step which is '98.8'

31    100000      3728380     37.3     98.8         result *= x

因此尝试减少阶乘 减半，以获得偶数，因此进行强度降低.

So tried to reduce the multiplication in factorial by half, for even number, hence doing Strength Reduction.

第二个半乘法代码:

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 = 1000 -- Total time: 0.00115 s

n = 10000-总时间:0.023636 s

for n = 10000 -- Total time: 0.023636 s

n = 100000-总时间:3.65019 s

for n = 100000 -- Total time: 3.65019 s

在中档显示有些改善，但在缩放方面并没有太大改善.

Which shows some improvement in the mid range but didn't improved much with scaling.

在此功能中，%%的大部分时间都花在了乘法上.

In this function too most of the %time is spent on multiplication.

61     50000      3571928     71.4     97.9         factorial *= next_multi.

所以我厌倦了删除尾随的零，然后相乘.

So I tired to remove the trailing zeros and then multiply.

没有尾随零代码.

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 s

For n = 1000 -- Total time: 0.061524 s

n = 10000-总时间:113.824 s

for n = 10000 -- Total time: 113.824 s

所以不是减少时间，而是由于字符串转换而增加了时间，因为'96 .2％'的时间也花在了

so instead of decreasing the time it's increasing the time because of the string conversion as also '96.2%' of the time is spend on that

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

所以我的问题是如何在不影响时间的情况下获取尾随零并有效地与shift配合使用.

So my question is how can i get the trailing zeros and use with shift efficiently without compromising the time.

所有分析均已完成. 基本操作系统(Linux):64位，内存:6GB

All the profiling done on. Elementary OS(Linux): 64bit, Ram : 6GB

推荐答案

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

首先，我建议使用素数分解来减少乘法的总数，因为小于x的素数大约是x/lnx.

First, I suggested using prime decomposition to reduct total number of multiplications because prime numbers smaller than x is about 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

for n = 10000, total time : 0.017s

n = 100000，总时间:2.047s

for n = 100000, total time : 2.047s

对于n = 500000，总时间:65.324s

for n = 500000, total time : 65.324s

(PS.在您的第一个程序中，对于n = 100000，我的计算机中总时间为3.454秒.)

(PS. in your first program, for n = 100000, total time is 3.454s in my machine.)

现在，让我们测试一下不带零的效率是否有效.尾随零的数量等于n!中素数因子5的数量. 程序是这样的

Now let's test whether it is efficient without trailing zero. The number of trailing zero equals the number of prime factors 5 in n!. The program is like this

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

for n = 10000, total time : 0.015s

n = 100000，总时间:1.896s

for n = 100000, total time : 1.896s

对于n = 500000，总时间:57.101s

for n = 500000, total time : 57.101s

它只是比以前快了一点.因此，没有尾随零似乎不是很有用

It is just a little faster than before. So Without trailing zero seems not very useful

这篇关于计算阶乘而不有效尾随零?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！