python中的大量阶乘 [英] Factorial of a large number in python

问题描述

这是我处理阶乘的方法：

Here's my approach to factorials:

def factorial(n):
    '''Returns factorial of n'''
    r = 1
    for i in range(1, n + 1):
        r *= i
    return r

我认为这很简单，尽管我想您可以提高效率，因为像100000这样的大数字需要很多时间。我的问题是吗？ math.factorial（）也不好，花费的时间大致相同。

I think it's pretty straightforward, though I guess you could make something more efficient, because it takes ages for large numbers like 100000. My question is, is there? math.factorial() is no good either, it takes roughly the same amount of time.

推荐答案

将数字依次相乘，

r = 1
for i in range(1, n + 1):
    r *= i
return r

非常快地创建大量（以万位计） ，然后您将有一个很大的数目和一个小的数目的许多乘法。至少其中一个因素是巨大的乘法运算很慢。

creates a large number (as in tens of thousands of bits) very quickly, and then you have a lot of multiplications of one huge number and one small number. Multiplications where at least one of the factors is huge are slow.

例如，您可以通过减少涉及大量数字的乘法运算的数量来显着加快运算速度。

You can speed it up considerably by reducing the number of multiplications involving huge numbers, for example

def range_prod(lo,hi):
    if lo+1 < hi:
        mid = (hi+lo)//2
        return range_prod(lo,mid) * range_prod(mid+1,hi)
    if lo == hi:
        return lo
    return lo*hi

def treefactorial(n):
    if n < 2:
        return 1
    return range_prod(1,n)

产生，计时 100000的计算！ ％100019 （我首先尝试了 len（str（fun（100000）），但是转换为字符串的速度非常慢，因此有所作为似乎比它还小）：

produces, timing the computation of 100000! % 100019 (I first tried len(str(fun(100000)), but the conversion to string is abominably slow, so that made the difference seem smaller than it is):

$ python factorial.py 
81430
math.factorial took 4.06193709373 seconds
81430
factorial took 3.84716391563 seconds
81430
treefactorial took 0.344486951828 seconds

因此 100000的速度提高了10倍以上！。

这篇关于python中的大量阶乘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！