我正在为自己开发一个小型Python程序,我需要一种算法来快速将一个巨大的数组与数字相乘(超过660 000个数字,每个数字都是9位数字)。结果数字超过400万位。目前我正在使用 math.prod,它可以在大约 10 分钟内计算出来,但这太慢了,特别是当我想增加数字数量时。
我检查了一些更快乘法的算法,例如 Schönhage–Strassen 算法和 Toom–Cook 乘法,但我不明白它们是如何工作的或如何制作它们。我尝试了在互联网上找到的一些版本,但它们运行得不太好,甚至更慢。我想知道是否有人知道如何更快地乘以这些数字,或者可以解释如何使用一些数学来做到这一点?
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)))