C++中整数如何相乘？

Question

我想了解C++中用于计算乘法的方法是什么。是否使用传统的竖式乘法算法？还是使用Fürer算法或Toom-Cook算法等其他算法？

我之所以想知道，是因为我需要计算非常大的数字并且需要高效率。因此，传统的竖式乘法算法O(n^2)可能效率过低，我需要采用其他乘法算法。

那么C++中使用的是哪种乘法算法呢？

- fdh

---

无论芯片做什么，它都会去执行。 - bmargulies

标题让我想起了整数繁殖的概念。 - harold

首先，他们必须进行所谓的“约会”。 - Manish

Answer 1

你好像漏掉了几个关键点：

1. 原生算术和大数算术是有区别的。
2. 你似乎对大数算术感兴趣。
3. C++不支持大数算术，基本数据类型通常是处理器的原生算术。

要获得大数（任意精度）算术，您需要自己实现或使用库。 （例如GMP）与Java和C#（等等）不同，C++没有用于任意精度算术的库。

所有那些花哨的算法:

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

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

---

无论如何，我不建议尝试实现大数库。我以前做过这个，很费事（特别是数学部分）。所以最好使用库。

- Mysticial

---

直到涉及非常大的数字，你在小学学习的方法在实践中表现更好。当然，你可以使用比10更大的基数。根据你的需求，2^32、2^64或者10^9都是方便的基数（以10为幂的基数在解析/打印基数为10的数字时很有用，而10^9是适合32位的最大幂）。 - R.. GitHub STOP HELPING ICE

Answer 2

你所说的“极大数”是什么意思？

C++和其他大多数编程语言一样，使用处理器内置的乘法硬件。具体如何工作并未在C++语言中指定。但对于普通整数和浮点数，您将无法在软件中编写更快的代码。

各种数据类型可以表示的最大数字因不同实现而异，但一些典型值为2147483647（int），9223372036854775807（long）和1.79769e+308（double）。

- Thomas Padron-McCarthy

Answer 3

在C++中，整数乘法由芯片处理。虽然我确信这样的库存在，但标准语言中没有Perl的BigNum的等效物。

- Joel

---

吹毛求疵：不一定。实现可以包括数字类型（甚至是int，尽管那应该很少见）而被针对的架构不支持，并且代之以将算术操作实现为调用运行时库。考虑128位整数或可能在32位系统上使用的64位整数。另外，过去有许多芯片没有浮点运算单元（FPU）。 - user395760

罕见但不是不存在：8位的6502处理器没有16位算术指令，因此CC65 C编译器必须通过8位指令序列和库调用来实现'int'算术运算。 - han

Answer 4

这完全取决于所使用的库和编译器。

- gangelo

Answer 5

这是在硬件中执行的。同样的道理，庞大的数字也行不通。C++在64位硬件中可以表示的最大数字是18446744073709551616。如果需要更大的数字，则需要使用任意精度库。

- Daniel

---

双精度浮点数怎么样？此外，大多数数据类型的确切大小取决于编译器。我还相信一些编译器提供128位整数类型。 - user395760

Answer 6

普通的C++使用CPU多指令（或者如果你的CPU没有这样的指令，则使用基于位移和加法的学校式乘法）。

如果您需要快速计算大数的乘积，我建议您查看GMP（http://gmplib.org），并使用gmpxx.h中的C++接口。

- Willem Hengeveld

Answer 7

如果你在编程中需要处理大量的数字，那么C++标准整数乘法将不再适用，你应该使用提供任意精度乘法的库，比如GMP http://gmplib.org/。

此外，在编写应用程序之前，你不必担心性能（过早优化）。这些乘法运算将会很快，而且很可能你软件中的许多其他组件会导致更多的减速。

- johanvdw

Answer 8

这些数字会有多大呢？即使是像Python这样的语言，也可以在标准处理器上以超过300万次每秒的速度使用任意精度整数进行1e100*1e100运算。这意味着将100个有效位数相乘只需要不到一百万分之一秒的时间。要把它放入上下文中，可观测宇宙中只有约10^80个原子。

首先写下你想要实现的目标，如果必要再进行优化。

- Dunes