整數如何在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++中相乘？

回答

相關問題