сложение вместо вычитания в алгоритме Кахана - PullRequest
Новая
       42

сложение вместо вычитания в алгоритме Кахана

8 голосов
/ 09 декабря 2011

Это алгоритм суммирования Кахана из Википедии : 

function KahanSum(input)
    var sum = 0.0
    var c = 0.0
    for i = 1 to input.length do
        y = input[i] - c    // why subtraction?
        t = sum + y
        c = (t - sum) - y
        sum = t
    return sum

Есть ли конкретная причина, по которой он использует вычитание (в отличие от сложения)?Если я поменяю местами операнды при вычислении c, могу ли я вместо этого использовать сложение?Каким-то образом это будет иметь для меня больше смысла: 

function KahanSum(input)
    var sum = 0.0
    var c = 0.0
    for i = 1 to input.length do
        y = input[i] + c    // addition instead of subtraction
        t = sum + y
        c = y - (t - sum)   // swapped operands
        sum = t
    return sum

Или есть какое-то странное различие между сложением и вычитанием с плавающей запятой, о котором я пока не знаю?

Кроме того, есть ли какое-нибудьРазница между (t - sum) - y и t - sum - y в исходном алгоритме?Разве круглые скобки не являются избыточными, поскольку - в любом случае является левоассоциативным?

Ответы [ 2 ]

2 голосов
/ 09 декабря 2011

Ваши два алгоритма эквивалентны. Единственной разницей во время исполнения будет знак c. Причина, по которой он использует сложение, заключается в том, что в версии Кахана c представляет ошибку, которая обычно является правильной минус вычисленное значение.

В том смысле, что в скобках указан порядок операций, скобки абсолютно необходимы. Фактически, именно они заставляют работать этот алгоритм!

Когда вычитание является левоассоциативным, как это имеет место в большинстве языков, a - b - c оценивается как (a - b) - c, поэтому оба значения одинаковы. Но вычитание в алгоритме Кахана равно a - (b - c), и это должно не быть оценено как a - b + c.

Сложение и вычитание с плавающей точкой не являются ассоциативными. Для выражений, эквивалентных стандартной арифметике, вы можете получить разные результаты в зависимости от порядка выполнения операций.

Для ясности давайте работать с точностью до 3 десятичных знаков. Это означает, что если мы получаем результат с 4 цифрами, мы должны округлить его. Теперь сравните (a - b) - c с математически эквивалентным a - (b + c) для некоторых конкретных значений: 

(998 - 997) - 5 = 1 - 5 = -4

с 

998 - (997 + 5) = 998 - Round(1002)
                = 998 - 1000 = -2

Итак, второй подход менее точен.

В алгоритме Кахана t и sum обычно будут относительно большими по сравнению с y. Таким образом, вы часто сталкиваетесь с ситуацией, как в примере выше, где вы получите менее точный результат, если не будете выполнять операции в правильном порядке.

2 голосов
/ 09 декабря 2011

Насколько я могу судить, ваш метод в точности эквивалентен методу из Википедии. Единственное отличие состоит в том, что знак c - и, следовательно, его значение - обратный. В алгоритме Википедии c является «неправильной» частью суммы; с = 0,0001 означает, что сумма немного больше, чем должна быть. В вашей версии c - это «исправление» к сумме; c = -0,0001 означает, что сумма должна быть немного меньше.

И я думаю, что скобки предназначены для удобства чтения. Они для нас, а не для машины.

...