執行數學公式時溢出問題

我聽說當計算平均值時，start +（end-start）/ 2與（start + end）/ 2不同，因爲後者可能導致溢出。我不太明白爲什麼第二個可能會導致溢出，而第一個不會。實施可避免溢出的數學公式的通用規則是什麼？執行數學公式時溢出問題

來源

2012-06-04 bit-question

你從哪裏「聽到」這個？提供一個引用。 – duffymo

我也看到這個地方。我認爲這可能是在Raymond Chen的The Old New Thing的帖子之一，除非我看到它檢查溢出。 – chris

如果這是整數 - 只標記它。 – moooeeeep

假設你正在使用計算機，其中最大整數值是10和要計算的5平均和7

第一種方法（開始+（端開始）/ 2），得到

5 + (7-5)/2 == 5 + 2/2 == 6

第二種方法（開始+結束）/ 2給出了一個溢出，因爲中間12的值超過了我們接受的最大值10並且「換行」到了其他東西（如果你使用的是無符號數通常會回到零，但如果你的號碼被簽名，你可以得到一個負數！）。

12/2 => overflow occurs => 2/2 == 1

當然，在如2^32而不是10大的值實際應用的計算機的整數溢出，但這個想法是一樣的。不幸的是，沒有「通用」方法來擺脫我所知道的溢出，而且這很大程度上取決於您使用的特定算法。然後，事情變得更加複雜。您可以根據您在引擎蓋下使用的數字類型獲得不同的行爲，除了溢出和溢出之外，還有其他類型的數字錯誤需要擔心。

來源

2012-06-04 13:48:51 hugomg

兩個您的公式將溢出，但在不同情況下：

當start和end都接近整數限制在該範圍的同一側的(start+end)/2式的(start+end)部分會溢出（即既有積極的也有消極的）。
當start爲正數，且end爲負數時，公式的(end-start)部分將會溢出，並且這兩個值都接近可表示的整數值的相應端點。

沒有「通用」規則，您可以逐案處理：查看部分公式，考慮可能導致溢出的情況，並想出避免它的方法。例如，可以顯示start+(end-start)/2公式，以避免在使用相同符號平均值時發生溢出。

這是艱難的方法;簡單的方法是使用更高容量的表示來獲得中間結果。例如，如果您使用long long而不是int來進行中間計算，並且只有在完成後纔將結果複製回int，則假設最終結果適合於int，您將避免溢出。

來源

2012-06-04 13:57:16 dasblinkenlight

在處理整數時，您可能會在採用這種策略時關心integer overflow。

請注意，使用公式b+(b-a)/2您需要確保a <= b。否則，您可能會在可能的值範圍的下限獲得相同的問題。考慮一下a/2+b/2。但是這種方法還有其他缺點。

當處理浮點數時會出現另一個問題，catastrophic cancellation。由於浮點表示的有效位數有限，當添加大量數據時（即使這只是一箇中間步驟），準確性會丟失。

爲了解決這個數值穩定性問題，例如，這種算法可以用來（從wikipedia稍微適應）：

def online_mean(data): 
    n = 0 
    mean = 0 

    for x in data: 
    n = n + 1 
    delta = x - mean 
    mean = mean + delta/n 

    return mean

不知何故，我覺得有一個你上述公式的關係......

來源

2012-06-04 13:58:42 moooeeeep

在二進制搜索，我們將編寫以下代碼：

if(start > end){ 
    return; 
} 
int mid = start + (end - start)/2;

使用start + (end - start)/2，我們能避免被@dasblinkenlight

當w指出的問題e使用(start + end)/2，它會像dasblinkenlight所示那樣溢出

來源

2013-08-19 06:00:58 rgc

執行數學公式時溢出問題

回答

相關問題