主页 / coding / 问题 / 78752268
Accepted
Sergio
Asked: 2024-07-16 07:55:52 +0800 CST

在 Python 中对大量数字进行乘法

  • 772

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

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

python

3 个回答

  1. Best Answer

    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[:split_at]) * recursive_prod(ns, r[split_at:])


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

  2. 我一直在使用一个比较棘手的方法，总是将最旧的两个尚未相乘的数字相乘，直到只剩下一个：

    from operator import mul

def prod(ns):
    ns = list(ns)
    it = iter(ns)
    ns += map(mul, it, it)
    return ns[-1]

    和@Ry- 的一样快。速度之所以快是因为 Karatsuba 在乘以两个大数而不是一个大数和一个小数时起作用。

    由于乘法算法更快，使用速度decimal似乎快了五倍（如果您愿意的话，还具有以十进制打印速度更快的优势）：

    from operator import mul
from decimal import *

setcontext(Context(prec=MAX_PREC, Emax=MAX_EMAX))

def prod(ns):
    ns = list(map(Decimal, ns))
    it = iter(ns)
    ns += map(mul, it, it)
    return ns[-1]
    • 3

  3. 有两个关键点可以加快速度。首先，使用你能得到的最快的 mult 实现。对于“足够大”的被乘数，Python 的 Karatsuba mult 是O(n^1.585)。该decimal模块更精致的 NTT mult 更像O(n log n)。但最快的方法是安装gmpy2扩展包，它包装了 GNU 的 GMP 库，其主要目标是达到峰值速度。它与 mult 具有基本相同的渐近性decimal，但常数因子较小。

    其次，高级乘法算法在将两个大小（位数）大致相同的大整数相乘时效果最佳。您可以将其留给运气，或者，如下所示，您可以使用优先级队列强制执行此操作，并在每一步中将剩余的“两个最小”部分乘积相乘。

    from gmpy2 import mpz
from heapq import heapreplace, heappop, heapify

# Assuming your input ints are in `xs`.
mpzs = list(map(mpz, xs))
heapify(mpzs)
for _ in range(len(mpzs) - 1):
    heapreplace(mpzs, heappop(mpzs) * mpzs[0])
assert len(mpzs) == 1
# the result is mpzs[0]

    这就是我要使用的代码。请注意，与巨型整数运算的成本相比，递归（本文未使用）的成本微不足道。堆操作比递归更昂贵，但仍然相对便宜，并且如果输入的顺序使得“运气好”的方法不够幸运，则可以大大超过其成本。

    • 3

相关问题