在整數乘法，然後分工

避免溢出我有兩個積分變量a和b和恆定s RESP。 d。我需要計算(a*b)>>s resp的值。 a*b/d。問題是乘法可能會溢出，並且即使a*b/d可以適合給定的整數類型，最終結果也不會正確。在整數乘法，然後分工

怎麼能有效解決？直接的解決方案是將變量a或b擴大爲更大的整數類型，但可能不會有更大的整數類型。有沒有更好的方法來解決這個問題？

我推斷'd'總是'1 << s'。真的嗎？ – 2011-04-04 17:26:28

是的，這是事實。 – 2011-04-04 17:30:22

你最好的選擇是擴大到一個更大的整數類型。 – 2011-04-04 17:31:32

如果沒有更大的類型，您需要找到一個big-int樣式庫，或者使用長乘法手動處理它。

例如，假設a和b是16位。然後，您可以將它們重寫爲a = (1<<8)*aH + aL和b = (1<<8)*bH + bL（其中所有單個組件都是8位數字）。然後你知道總體結果如下：

(a*b) = (1<<16)*aH*bH 
     + (1<<8)*aH*bL 
     + (1<<8)*aL*bH 
     + aL*bL

這4個組件中的每一個都適合一個16位寄存器。您現在可以執行例如在每個組件上右移，小心處理適當的進行。

2011-04-04 17:34:03

我認爲問題所述是a * b可能不適合16位，雖然a * b/d是保證以適應。因此，您的解決方案無濟於事。 – 2011-04-04 17:40:42

@Mark Ransom：確實如此。用我的方法，你不需要32位的值。 – 2011-04-04 17:42:52

是的，這可行，但在這個解決方案中似乎有一些浪費的計算。我想知道它是否無法以某種方式與分部合併（右移）以獲得更高效的代碼。 – 2011-04-04 17:44:14

我還沒有徹底測試，但你可以做的劃分，再佔其餘部分，在額外的操作爲代價？由於d是2的冪，因此所有的分區都可以簡化爲按位運算。

例如，總是假定a > b（你想先分割更大的數字）。然後a * b/d = ((a/d) * b) + (((a % d) * b)/d)

2011-04-04 17:40:39

我認爲'（a％d）* b'仍然可能溢出（最大的可能值是'（d-1）* b'）。 – 2011-04-04 17:50:27

您可以使用與標記B爲（（a％d）* b）/ d部分解釋的相同技術，將％d視爲b，將b視爲a。 – steabert 2011-04-04 17:54:37

@steabart：是的，的確如此。爲了安全起見，您需要多次遞歸。 – 2011-04-04 18:08:32

如果較大的類型只是64位，那麼直接的解決方案將最有可能導致高效的代碼。在x86 CPU上，任何兩個32位數的乘法都會導致另一個寄存器溢出。所以如果你的編譯器明白這一點，它可以生成Int64 result=(Int64)a*(Int64)b的高效代碼。

我在C＃中遇到了同樣的問題，編譯器生成了相當不錯的代碼。而C++編譯器通常創建比.net JIT更好的代碼。

我建議用強制類型轉換的代碼寫入到更大的類型，然後檢查生成的彙編代碼來檢查它是否是好的。

2011-04-04 17:42:29 CodesInChaos

我看過反彙編和'int32_t結果=（int64_t（a）* int64_t（b））>> 2'產生很好的代碼（只是'imul'乘法）。但是當b不變時，編譯器會生成'call _allmul'。這似乎有點奇怪。我將不得不深入研究它。 – 2011-04-04 20:41:07

在某些情況下（LCG歷史隨機數生成器與選定的常數），就可以做你想做的，爲a和d一些值。

這被稱爲施拉格的方法，參見例如。 there。

2011-04-05 10:53:07

回答