在C++中，整数是如何乘法的？

Question

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

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

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

Answer 1

您似乎在这里遗漏了几个关键的东西：

arithmetic.

• You似乎对bignum感兴趣，

1. arithmetic.
2. C++不支持bignum<>E213>算法。原生bignum算法和bignum算法之间存在差异。似乎对bignum感兴趣。基本数据类型通常是处理器的原生算法。

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

所有这些花哨的算法：

O(n^1.585)

• Toom-Cook：< O(n^1.465)

• FFT-based：~ O(n log(n))

：

• Karatsuba

仅适用于在bignum库中实现的bignum算法。处理器用于其本机算术操作的内容多少有些无关紧要，因为它通常是恒定的时间。

在任何情况下，我都不建议您尝试实现一个bignum库。我以前做过，这是相当苛刻的(特别是数学)。所以你最好使用一个库。

Answer 2

你说的“非常大的数字”是什么意思？

与大多数其他编程语言一样，C++使用处理器中内置的乘法硬件。C++语言并没有详细说明这是如何工作的。但是对于普通的整数和浮点数，你将无法在软件中写出更快的东西。

不同的数据类型可以表示的最大数字在不同的实现中可能有所不同，但是一些典型的值是：int为2147483647，long为9223372036854775807，double为1.79769e+308。

Answer 3

在C++中，整数乘法是由芯片处理的。在标准语言中没有与Perl的BigNum等价物，尽管我确信这样的库确实存在。