Chi*_*ing 6 algorithm multiplication
我需要尽可能有效地乘以几个大的长整数。
\n我正在尝试实现 Harvey & van der Hoeven 2019 整数乘法算法，但我一直坚持理解其背后的定义和数学，特别是 Agarwal\xe2\x80\x93Cooley 算法。
\n任何有助于理解该算法的帮助，例如实际示例或一些伪代码，将不胜感激。
\nRic*_*ard 13
记住大 O 符号定义是存在一些 x\xe2\x89\xa5x\xe2\x82\x80 ，其中某个函数 |f(x)|\xe2\x89\xa4\xce\xb5g(x) 对于所有这样的x。
\nHarvey & van der Hoeven (2019) 算法的问题在于涉及的 x\xe2\x82\x80 相当大。因此，对于大多数输入，他们的算法提供了一种低效地乘以整数的方法。不过，对于非常大的数字，该算法确实给出了O(n log n)算法。
\n但这些数字有多大呢？作者之一大卫·哈维 (David Harvey)指出：
\n\n\n新算法目前的形式并不实用，因为我们论文中给出的证明只适用于大得可笑的数字。即使每个数字都写在氢原子上，可观测宇宙中也几乎没有足够的空间来写下它们。
\n另一方面，我们希望通过进一步改进，该算法可能适用于仅数十亿或数万亿位数的数字。如果是这样，它很可能成为计算数学家武器库中不可或缺的工具。
\n
因此，如果你认真对待你既定的目标——快速乘以大数——这个算法不是你应该做的方式。
\n