計算可能溢出的整數運算的最安全和最有效的方法

Question

假設我們有2個常量A & B和變量i，所有64位整數。我們要計算一個簡單常見的算術運算，例如：

i * A/B (1) 

爲了簡化問題，我們假設變量i始終處於範圍[INT64_MIN*B/A, INT64_MAX*B/A]，使運算的最終結果（1）不不溢出（即：適合，範圍[INT64_MIN, INT64_MAX]）。

此外，i被假定爲更可能在友好範圍範圍1 = [INT64_MIN/A, INT64_MAX/A]（即：接近0），然而i可以是（不容易）在該範圍之外。在第一種情況下，i * A的平凡整數計算不會溢出（這就是爲什麼我們將範圍稱爲友好的）;在後一種情況下，i * A的平凡整數計算會溢出，導致（1）的計算中出現錯誤的結果。 （1）（其中「最安全」是指：保持正確或至少有一個體面的精度，而「最有效」的意思是：最低平均值的意思是：最安全的和最有效的方式計算時間），提供i更有可能在友好範圍範圍1。

在現在，目前在代碼中實現的解決方案是以下之一：

(int64_t)((double)A/B * i) 

該解決方案是相當安全的（沒有溢出），雖然不準確（精度損失，由於雙尾數53位的限制），相當速度很快，因爲在編譯時預計算雙分區(double)A/B，因此只能在運行時計算雙倍值。

Answer 1

爲了給這個問題提供一個量化的答案，我在這篇文章中提出了不同解決方案的基準作爲本文提出的解決方案的一部分（感謝評論和答案）。

不同的實現的基準測量計算時間，當i是友好範圍內範圍1 = [INT64_MIN/A, INT64_MAX/A]，當i是友好範圍外（但在安全範圍範圍2 = [INT64_MIN*B/A, INT64_MAX*B/A]）。

每個實現執行「安全」（即，沒有溢出）運算的計算：i * A/B（第一次執行除外，給出爲參考計算時間）。但是，某些實現可能會返回偶然不準確的計算結果（通知哪種行爲）。

提出的一些解決方案尚未經過測試或未在下文中列出;這些是：使用__int128（不受ms vc編譯器支持）的解決方案，但已使用升級int128_t代替;解決方案使用擴展的80位long double（不受ms vc編譯器支持）;解決方案使用InfInt（工作和測試，但速度太慢，不能成爲一個體面的競爭對手）。

時間測量值以ps/op（皮秒每次操作）指定。基準平臺是Windows 7 x64下的英特爾Q6600 @ 3GHz，可執行文件使用MS vc14，x64 /發佈目標進行編譯。下文所引用的變量，常量和函數被定義爲：

int64_t  i; 
const int64_t A  = 1234567891; 
const int64_t B  = 4321987; 
inline bool in_safe_range(int64_t i) { return (INT64_MIN/A <= i) && (i <= INT64_MAX/A); } 

1. (i * A/B) [參考]
   在範圍1 I：1469個PS/OP，我外範圍1： 無關（溢出）
   
2. ((int64_t)((double)i * A/B))
   我在範圍1：10613 PS/OP，我外範圍1：10606 PS /運算
   注：不頻繁不準確的結果（最大誤差= 1位），在整個範圍範圍2
   
3. ((int64_t)((double)A/B * i))
   我在範圍1：1073個PS/OP，我外範圍1：在整個範圍範圍2
   注意不頻繁的不準確的結果（最大誤差= 1個比特）：編譯器可能1071 PS /運算
   注預先計算(double)A/B導致觀察到的性能提升vs以前的解決方案。
   
4. (!in_safe_range(i) ? (int64_t)((double)A/B * i) : (i * A/B))
   我在範圍1：2009 PS/OP，我外範圍1：1606 PS /運算
   注：稀有不準確的結果（最大誤差= 1個比特）外範圍1
   
5. ((int64_t)((int128_t)i * A/B)) [助力int128_t]
   我在範圍1：89924 PS/OP，我外範圍1：89289 PS/OP
   注：提升int128_t執行板凳平臺上的顯着差（不知道爲什麼）
   
6. ((i/B) * A + ((i % B) * A)/B)
   我在範圍1：5876個PS/OP，我外範圍1：5879 PS /運算
   
7. (!in_safe_range(i) ? ((i/B) * A + ((i % B) * A)/B) : (i * A/B))
   我在範圍1：1999 PS/OP，我外範圍1：6135個PS /運算
   

Conclusion
a) If slight computation errors are acceptable in the whole range Range2, then solution (3) is the fastest one, even faster than the direct integer computation given as reference.
b) If computation errors are unacceptable in the friendly range Range1, yet acceptable outside this range, then solution (4) is the fastest one.
c) If computation errors are unacceptable in the whole range Range2, then solution (7) performs as well as solution (4) in the friendly range Range1, and remains decently fast outside this range.

Answer 2

我想你可以在溢出發生之前檢測溢出。在你的情況下，i * A/B，你只是擔心i * A部分，因爲師不能溢出。

您可以通過執行bool overflow = i > INT64_MAX/A的測試來檢測溢出。您將不得不根據操作數和結果的符號進行修改。

Answer 3

某些實現允許__int128_t。檢查您的實施是否允許，以便您可以將其用作佔位符而不是double。請參考以下職位：
Why isn't there int128_t?

---

如果不是很在意「快」 -ness，那麼良好的便攜性，我建議用頭只有C++庫"InfInt"。

It is pretty straight forward to use the library. Just create an instance of InfInt class and start using it:

InfInt myint1 = "15432154865413186646848435184100510168404641560358"; 
InfInt myint2 = 156341300544608LL; 

myint1 *= --myint2 - 3; 
std::cout << myint1 << std::endl; 

Answer 4

如果你不能得到所涉及的範圍更好界限，那麼你最好關閉以下iammilind's advice使用__int128。

原因是，否則你將不得不通過分詞來實現雙字乘法和雙字的完整邏輯。英特爾和AMD處理器手冊包含有用的信息和現成的代碼，但是它非常複雜，並且使用C/C++而不是彙編程序使事情變得更加複雜。

所有優秀的編譯器都將有用的原語公開爲內在函數。 Microsoft's list似乎沒有包含類似於多分類器的基元，但內部函數爲128位產品提供了兩個64位整數。基於此，您可以執行長兩位數除以一位數字，其中一位數字將是一個64位整數（通常稱爲「肢體」，因爲大於一位數字，但仍只是整體的一部分）。仍然相當參與，但比使用純C/C++更好。然而，可移植性不如直接使用__int128。至少這樣，編譯器實現者已經爲你做了所有的辛苦工作。

如果你的應用領域可以給你有用的界限，像(u % d) * v不會再溢出你可以使用身份

(u * v)/d = (u/d) * v + ((u % d) * v)/d 

其中/表示整數除法，只要u是爲非負d是正面的（否則你可能會違背允許運營商%的語義的餘地）。

在任何情況下，您都可能需要分離出操作數的符號，並使用無符號操作來找到更多有用的機制，或者避免編譯器的破壞，比如您提到的飽和乘法。有符號整型操作的溢出調用未定義的行爲，編譯器可以自由地執行任何他們想要的操作。相比之下，無符號類型的溢出是明確定義的。

而且，與無符號類型，你可以求助於像與s = a (+) b規則（其中(+)可能是，溢出的無符號加法），你將有要麼s == a + b或s < a && s < b，它可以讓你用廉價的操作事後檢測溢出。

然而，在這條道路上你不太可能走得更遠，因爲需要付出的努力很快接近 - 甚至超過 - 實現我之前提到的雙肢手術的努力。只有對應用程序域進行全面分析才能提供規劃/部署此類快捷方式所需的信息。在一般情況下和你遇到的界限你幾乎不走運。

Answer 5

不確定值的範圍，請問(i/B) * A + (i % B) * A/B有幫助嗎？