355
правок
Изменения
→Простое суммирование
Проблема с использованием этой процедуры заключается в требовании <tex>|a| \geqslant |b|</tex>. Если это заранее не известно, то необходимо выполнить сравнение перед ее вызовом. В большинстве С компиляторов, возможно, самым быстрым переносимым способом реализовать эту проверку является выражение <tex>if ((a > b) == (a > -b))</tex>. На эту проверку уйдет некоторое время, но увеличение времени может быть на удивление большим из-за современных процессоров с суперскалярными и конвейерными архитектурами, в которых вызов условного оператора может сбросить ветку предсказаний.
Это объяснение лишь гипотетическое и зависит от машины, но алгоритм TwoSum, что будет описан ниже, избегает этого сравнения посредством трех дополнительных операций, что обычно на практике даже быстрее. Конечно же, FastTwoSum все же быстрее, если результат сравнения известен ''априори''.
{{Теорема
|author=
Knuth
|statement=
Пусть <tex>a</tex> и <tex>b</tex> есть <tex>p</tex>-битные числа, причем <tex>|a| \geqslant |b|</tex>. Тогда следующий алгоритм вернет непересекающееся расширение <tex>x + y</tex> такое, что <tex>a + b = x + y</tex>, где <tex>x</tex> - приближение (аппроксимация) суммы <tex>a + b</tex>, а <tex>y</tex> представляет собой ошибку округления при вычислении <tex>x</tex>.
}}
Псевдокод:
<tex>TwoSum(a, b)</tex>
<tex>1</tex> <tex>x \Leftarrow a \oplus b</tex>
<tex>2</tex> <tex>b_{virtual} \Leftarrow x \ominus a</tex>
<tex>3</tex> <tex>a_{virtual} \Leftarrow x \ominus b_{virtual}</tex>
<tex>4</tex> <tex>b_{roundoff} \Leftarrow b \ominus b_{virtual}</tex>
<tex>5</tex> <tex>a_{roundoff} \Leftarrow a \ominus a_{virtual}</tex>
<tex>6</tex> <tex>y \Leftarrow a_{roundoff} \oplus b_{roundoff}</tex>
<tex>7</tex> <tex>return (x, y)</tex>
