355
правок
Изменения
→Expansion sum
[[Файл:Adaptive_7.jpg|слева|Рисунок к теореме Деккера]]
<br clear="all" />
====Fast expansion sum====
<wikitex>
{{Теорема
|statement=
Пусть $e = \sum^{m}_{i=1}e_i$ и $f = \sum^{n}_{i=1}f_i$ - строго неперекрывающиеся $m$- и $n$-компонентные расширения, компоненты которых - $p$-битные числа, где $p \geqslant 4$. Предполагается, что компоненты обоих расширений отсортированы в '''возрастающем''' порядке, причем все компоненты ненулевые. Тогда следующий алгоритм,запущенный на машине с правилом округления до ближайшего четного, вернет такое расширение $h$, что $h = \sum^{m + n}_{i=1}h_i = e + f$, где компоненты $h$ также отсортированы в возрастающем порядке и не равны нулю. Алгоритм также сохраняет свойство несмежности/неперекрываемости.
}}
Псевдокод для суммы:
$ExpansionSum(e, f)$
$1$ $Merge$ $e$ $and$ $f$ $into$ $a$ $single$ $sequence$ $g$, $in$ $order$ $of$ $nondecreasing$ $magnitude$ $(possibly$ $with$ $interspersed$ $zeros)$
$2$ $(Q_i, h_1) \Leftarrow FastTwoSum(g_2, g_1)$
$3$ $for$ $i = 3 \dots (n+m)$
$4$ $(Q_i, h_{i-1}) \Leftarrow TwoSum(Q_{i-1}, g_i)$
$5$ $h_{n+m} \Leftarrow Q_{m+n}$
$6$ $return$ $h$
</wikitex>
[[Файл:Adaptive_8.jpg|слева|Рисунок к теореме Деккера]]
<br clear="all" />
</wikitex>
