python - python什么时候开始使用不同的算法进行大乘法？

我目前在一个算法类中，有兴趣看看两种方法中哪一种可以使一个大数列表相乘，从而获得更快的运行时间我发现递归乘法的执行速度快了10倍。对于下面的代码，我得到t_sim=53.05s和t_rec=4.73s。我做了一些其他测试，它们似乎都在10倍的范围内。
此外，您可以将递归乘法中的值放入树中，并重用它们，以更快地计算列表子集的乘法。
我做了一个理论上的运行时分析，两个都是n^2，使用标准乘法，但是当使用karatsuba算法时，这个系数降到n^log_2（3）。
简单乘法中的每个乘法都应该有运行时i*1。在i=1…n上求和，我们得到一个算术级数，可以用高斯公式得到n*（n+1）/2=o（n^2）。
对于第二个，我们可以看到给定递归级别的乘法时间是（2^d）^2，其中d是深度，但只需要乘以n*2^-d值这些层最终形成一个几何级数，其中每个层的运行时间为n*2^d，最终深度为log 2（n）。几何级数的解是n*（1-2^log 2（n））/（1-2）=n*（n-1）=o（n^2）。如果使用karatsuba算法，则可以通过执行相同的方法获得O（n^log_2（3））
如果代码使用的是karatsuba算法，那么加速是有意义的，但似乎没有意义的是两个运行时之间的线性关系，这使得python似乎使用的是标准乘法，根据wikipedia的说法，在使用500位以下的位时，标准乘法更快（我在下面的代码中使用了2^23位每一个数字实际上都有1兆字节长）

import random
import time

def simple_multiply(values):
    a = 1
    for val in values:
        a *= val
    return a

def recursive_multiply(values):
    if len(values) == 1:
        return values[0]
    temp = []
    i = 0
    while i + 1 < len(values):
        temp.append(values[i] * values[i+1])
        i += 2
    if len(values) % 2 == 1:
        temp.append(values[-1])
    return recursive_multiply(temp)

def test(func, values):
    t1 = time.time()
    func(values)
    print( time.time() - t1)

def main():
    n = 2**11
    scale = 2**12
    values = [random.getrandbits(scale) for i in range(n)]
    test(simple_multiply, values)
    test(recursive_multiply, values)
    pass

if __name__ == '__main__':
    main()

最佳答案

两个版本的代码都有相同的乘法数，但在简单版本中，每个乘法平均长度约为2000位。
在第二个版本中，N/2乘法是24位长，N/4是48位长，N/8是96位长，等等。平均长度只有48位。

关于python - python什么时候开始使用不同的算法进行大乘法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52973664/