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

Question

我想知道在C++中使用什么样的方法来乘以数字.这是传统的教科书长期乘法吗？富勒的算法？Toom-Cook？

我在想,因为我需要增加极大的数字,并且需要高效率.因此,传统的教科书长期乘法O(n^2)可能效率太低,我需要采用另一种乘法方法.

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

Answer 1

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

1. 本机算术和bignum算术之间存在差异.
2. 你似乎对bignum算术很感兴趣.
3. C++不支持bignum算法.原始数据类型通常是处理器的本机算法.

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

所有这些花哨的算法:

• Karatsuba: O(n^1.585)
• TOOM库克: < O(n^1.465)
• 基于FFT的: ~ O(n log(n))

仅适用于在bignum库中实现的bignum算法.处理器用于其本机算术运算的内容有点无关紧要,因为它通常是恒定的时间.

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