Python 中大量数字的乘法

Question

我正在为自己开发一个小型Python程序，我需要一种算法来快速将一个巨大的数组与数字相乘（超过660 000个数字，每个数字都是9位数字）。结果数字超过400万位。目前我正在使用 math.prod，它可以在大约 10 分钟内计算出来，但这太慢了，特别是当我想增加数字数量时。

我检查了一些更快乘法的算法，例如 Schönhage–Strassen 算法和 Toom–Cook 乘法，但我不明白它们是如何工作的或如何制作它们。我尝试了在互联网上找到的一些版本，但它们运行得不太好，甚至更慢。我想知道是否有人知道如何更快地乘以这些数字，或者可以解释如何使用一些数学来做到这一点？

Answer 1

math.prod

将一次累积一个产品编号。您可以通过递归划分列表来做得更好。

这对我来说只需几秒钟即可运行：

import math


def recursive_prod(ns, r):
    if len(r) <= 10:  # arbitrary small base case
        return math.prod(ns[i] for i in r)

    split_at = len(r) // 2
    return recursive_prod(ns, r[:s]) * recursive_prod(ns, r[s:])


import random
ns = [random.randrange(1_000_000_000) for _ in range(660_000)]
p = recursive_prod(ns, range(len(ns)))