python – 有效地计算阶乘而没有尾随零？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python – 有效地计算阶乘而没有尾随零？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3675字，纯文字阅读大概需要6分钟。

内容图文

我正在努力改善大数的因子计算的运行时间.

第一个简单循环和乘法的代码.

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′

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

此功能的配置结果：

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.

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

没有尾随零代码.

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

所以我的问题是如何在不影响时间的情况下有效地使用尾随零和使用移位.

所有的分析都完成了.
基本操作系统(Linux)：64位,Ram：6GB

解决方法:

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

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

(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)

for n = 10000, total time : 0.015s

for n = 100000, total time : 1.896s

for n = 500000, total time : 57.101s

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

内容总结

以上是互联网集市为您收集整理的python – 有效地计算阶乘而没有尾随零？全部内容，希望文章能够帮你解决python – 有效地计算阶乘而没有尾随零？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端