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

我想知道在C++中使用哪种方法将数字相乘。是传统的教科书长乘法吗？ Fürer's algorithm？ Toom-Cook？

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

那么C++使用哪种乘法呢？

最佳答案

您似乎在这里错过了一些关键的事情:

本地的算术与 bignum 算术之间是有区别的。

您似乎对 bignum 算术感兴趣。

C++不支持 bignum 算术。基本数据类型通常是处理器的 native 算术。

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

所有这些花哨的算法:

唐津:O(n^1.585)

Toom-Cook:< O(n^1.465)

基于FFT:~ O(n log(n))

仅适用于在bignum库中实现的bignum算术。处理器用于其 native 算术运算的内容是不相关的，因为它是
通常是固定时间。

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

关于c++ - 整数如何在C++中相乘？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9649283/