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

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

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

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

来源

2012-03-10 fdh

+13

无论芯片做什么，它都可以。 – bmargulies 2012-03-10 19:07:15

标题让我想到整数再现:) – harold 2012-03-10 19:20:13

@harold首先他们必须做一些叫做“约会”的事情。 – Manish 2012-03-10 20:55:43

你似乎在这里失去了一些关键的东西：

有本地算术和BIGNUM算术之间的差异。
您似乎有兴趣bignum算术。
C++不支持bignum算术运算。原始数据类型通常为处理器的算术运算。

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

所有这些花哨的算法：

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

仅适用于BIGNUM被实现算术在高档图书馆。处理器用于其本地算术运算的东西有点不相关，因为它通常是不变的时间。

在任何情况下，我不建议你尝试实现BIGNUM库。我以前做过，而且要求很高（尤其是数学）。所以你最好使用一个库。

来源

2012-03-10 19:08:56 Mysticial

+1用于猜测OP的意图:-) – hirschhornsalz 2012-03-10 19:28:37

直到你达到非常大的数字，你在小学时学到的方法在实践中表现会更好。当然你使用的基数大于10。:-)根据您的需要，2^32,2^64或10^9可以构成方便的基数（10的幂在分析/打印基数10时非常有用，这对优化非常重要，而10^9是最大功率，适合32位）。 – 2012-03-10 21:09:35

这一切都取决于使用的库和编译器。

来源

2012-03-10 19:07:07 gangelo

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

来源

2012-03-10 19:07:59 Joel

挑剔：不一定。对于实现来说，包含数字类型（甚至是'int'，尽管*这应该是非常罕见的）是完全可能的，而架构所针对的数据类型不支持这些数字类型，而是对它们执行算术运算，作为对某些运行时库的调用。考虑32位系统上的128位整数或可能的64位整数。而且，以前有很多没有浮点单元（FPU）的芯片。 – delnan 2012-03-10 19:11:15

@delnan：罕见但并非不存在：8位6502处理器没有16位算术指令，因此CC65 C编译器必须通过8位指令和库调用序列实现“int”算术。 – han 2012-03-11 07:33:40

你是什么意思“极大数量”？

与大多数其他编程语言一样，C++使用内置于处理器中的乘法硬件。 C++语言没有指定具体的工作方式。但是对于正常的整数和浮点数，你将无法用软件更快地写出东西。

可以由各种数据类型来表示可在不同实施方式之间变化的最大数字，但一些典型值是2147483647 INT，9223372036854775807为长，和1.79769e + 308 双。

来源

2012-03-10 19:08:37

它在硬件中执行。出于同样的原因，巨大的数字将无法工作。在64位硬件中，C++可以表示的最大数量是18446744073709551616.如果你需要更大的数字，你需要一个任意的精度库。

来源

2012-03-10 19:09:42 Dani

双打怎么样？此外，大多数数据类型的确切大小取决于编译器。我也相信一些编译器提供128位整数类型。 – delnan 2012-03-10 19:13:23

纯C++使用CPU MULT指令（使用bitshifts和补充，如果你的CPU不具备这样的指令或教科书乘法。）

如果您需要大量快速繁殖，我建议看GMP（http://gmplib.org ），如果你有大量的在C工作标准的整数乘法++将不再工作，你应该使用提供任意精度的乘法，如GMP http://gmplib.org/

还设有图书馆使用C++接口从gmpxx.h

来源

2012-03-10 19:11:27

，在编写应用程序之前，您不应该担心性能（=过早优化）。这些乘法运算速度会很快，而且软件中很多其他组件可能会导致更多的放缓。

来源

2012-03-10 19:12:37 johanvdw

这些数字会有多大？即使像Python这样的语言也可以在标准处理器上以每秒300万次以上的任意精度整数执行1e100*1e100。这增加了100个重要位置的时间少于百万分之一秒。为了说明这一点，在可观察的宇宙中只有大约10^80个原子。

先写下你想要达到的要求，然后再进行优化。

来源

2012-03-10 19:21:45 Dunes

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

回答

相关问题