高效计算没有末尾零的阶乘？

Question

高效计算没有末尾零的阶乘？

pythonalgorithmoptimizationprofilingfactorial

4

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

第一种代码是简单地循环并相乘。

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 秒。

从对 n = 100000 的线性分析中可以看出，大部分 %time 花费在乘法步骤上，占'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秒

这表明该函数在中等规模上有所改善，但随着规模的增大改善不明显。

在这个函数中，大部分%time都花费在乘法上。

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')).

所以我的问题是如何在不影响时间的情况下有效地获取尾随零并与移位一起使用。

所有的分析都在Elementary OS(Linux)上进行：64位，内存：6GB。

- Ankur Anand

我认为质因数分解会很有帮助。 - throwit

2个回答

0

我不确定这个方法是否能解决你的问题，但你可以尝试一下这个方法：

我看到你需要计算10^4的阶乘（最大值），所以：

创建筛法选出10000以内的所有素数。
对1到10000之间的所有数字进行质因数分解，并将结果存储在数组中。（这两个步骤不应该占用太多时间）
现在你将恰好拥有1229个素数和它们的幂。
获取所有素数的幂并相乘。对于长数字，这将将乘法操作的数量从10000减少到1229。（但与此同时，它将需要一些时间来查找幂）

附注:（我不是很熟悉Python，否则我会亲自实现的）

- vish4071

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- throwit · Accepted Answer

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

首先，我建议使用质因数分解来减少总乘法次数，因为小于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.017秒

n = 100000时，总时间: 2.047秒

n = 500000时，总时间: 65.324秒

(PS. 在你的第一个程序中，当n=100000时，在我的电脑上总时间为3.454秒。)

现在让我们测试一下不带尾随零是否高效。尾随零的数量等于n!中质因数5的数量。

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.015秒

当n = 100000时，总时间为1.896秒

当n = 500000时，总时间为57.101秒

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