c++ - C++中整数如何相乘？

Question

我想知道在C++中用什么样的方法来乘以数字。是传统教科书的长乘法吗？ Fürer's algorithm ？ Toom-Cook ？

我想知道，因为我将需要乘以非常大的数字并且需要很高的效率。因此，传统的教科书长乘法 O(n^2) 可能效率太低，我需要求助于另一种乘法。

那么C++使用什么样的乘法呢？

Answer 1

您似乎在这里遗漏了几件重要的事情:

1. native 算术与 bignum 算术之间存在差异。
2. 您似乎对bignum 算术感兴趣。
3. C++ 不支持 bignum 算术。原始数据类型通常是处理器的原生算法。

要获得 bignum(任意精度)算术，您需要自己实现或使用库。 (例如 GMP)与 Java 和 C#(以及其他)不同，C++ 没有用于任意精度算术的库。

所有那些花哨的算法:

• 唐翼:O(n^1.585)
• Toom-Cook:< O(n^1.465)
• 基于 FFT:~ O(n log(n))

仅适用于在 bignum 库中实现的 bignum 算术。处理器用于其 native 算术运算的内容有点无关紧要，因为它是 通常是常数时间。

---

无论如何，我不建议您尝试实现一个 bignum 库。我以前做过，而且要求很高(尤其是数学)。所以你最好使用图书馆。