355
правок
Изменения
→Expansion sum
====Expansion sum====
<wikitex>
{{Теорема
|statement=
Пусть $e = \sum^{m}_{i=1}e_i$ и $f = \sum^{n}_{i=1}f_i$ - неперекрывающиеся $m$- и $n$-компонентные расширения, компоненты которых - $p$-битные числа, где $p \geqslant 3$. Предполагается, что компоненты обоих расширений отсортированы в '''возрастающем''' порядке, причем все компоненты ненулевые. Тогда следующий алгоритм вернет такое расширение $h$, что $h = \sum^{m + n}_{i=1}h_i = e + f$, где компоненты $h$ также отсортированы в возрастающем порядке и не равны нулю. Алгоритм также сохраняет свойство несмежности/неперекрываемости.
}}
Псевдокод для суммы:
$ExpansionSum(e, f)$
$1$ $h \Leftarrow e$
$2$ $for$ $i = 1 \dots n$
$3$ $\langle h_i, h_{i+1}, \dots, h_{i+m} \rangle \Leftarrow GrowExpansion(\langle h_i, h_{i+1}, \dots, h_{i+m-1} \rangle, f_i)$
$4$ $return$ $h$
</wikitex>
