計算最精確的結果：固定點核心列表的總和

可以說你必須添加一些存儲在一個巨大的陣列中的32位定點數L，並且你希望得到最準確的結果儘可能的結果。此外，您不得使用除L和32位定點數之外的任何內容（即不允許將它們轉換爲64位）。如何獲得L中數字總和的最準確結果？計算最精確的結果：固定點核心列表的總和

這將是我目前的做法在須藤代碼注意：

L = sort(L) 
result = 0 
lastMax = false -- indicates whether we've extracted the maximum from L last time 

while (not empty(L)) and (result not equals +INF or -INF) do: 
    current = 0 
    if lastMax: 
    current = extractMin(L) -- gets and removes minimum from L 
    else: 
    current = extractMax(L) -- gets and removes maximum from L 
    result = safeAdd(result, current) 
    lastMax = not lastMax 

safeAdd(a,b): 
    if a = +INF: return +INF 
    else if a = -INF: return -INF 
    else: return a + b

所以我從剩下的列表L添加的最小/最大，以保持L的範圍的方式之間交替如何實現safeAdd表明，一旦我們越過了精度範圍（即，a+b的結果已經產生了+INF或-INF - 就像它在C中完成一樣），我們不會再改變結果。

對於如何改進方法，您有什麼建議嗎？

旁註：如果我們要非常精確：我們進一步假設+操作可以產生+INF或-INF可表示爲編程語言的點數。但我們假設值+INF,-INF不會發生在L。我們忽略了定點標準也可能具有NaN的表示。

來源

2016-05-18 ndrizza

你有沒有考慮[Kahan的總和] （https://en.wikipedia.org/wiki/Kahan_summation_algorithm）？ –

感謝您的提示！我很抱歉，但我只能將問題從浮點數轉換爲定點數。所以這可能不再相關。 – ndrizza

@ndrizza定點添加僅僅是整數的加法，所以在這個操作中沒有發生錯誤（即它是確切的），除非有溢出，這是一個有點不同的問題，可能通過根據用例重新縮放來解決。常用的定點格式不提供無限的表示。 – njuffa

如果你知道，結果是在範圍內，你不需要關心上溢或下溢。

這裏是4位的例子只是爲了保持它的簡單

7 0111 
+1 0001 
= 1000 <-- -8 overflow 
-1 0001 
= 0111

如果你不知道，如果結果是在範圍內，則需要溢出和下溢計數。

對於A = B + C

溢出如果b和c是正的和爲負

下溢，如果b和c爲負並且a是正

來源

2016-06-08 16:15:24 maniacmic

計算最精確的結果：固定點核心列表的總和

回答

相關問題