355
правок
Изменения
→Алгоритмы суммирования
==Алгоритмы суммирования==
===Простое суммирование===
Важной базовой операцией во всех алгоритмах, основанных на представлении чисел в виде расширений, является сумма двух <tex>p</tex>-битных величин, результатом которой является расширение длины два. Есть два алгоритма для выполнения этой задачи - алгоритмы Деккера и Кнута.
{{Теорема
|author=
Dekker
|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>Fast-Two-Sum(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>y \Leftarrow b \ominus b_{virtual}</tex>
<tex>4</tex> <tex>return (x, y)</tex>
{{TODO |t=add pictures}}
