Изменения
→Суммирование разложений
===Суммирование разложений===
<wikitex>
Базируясь на алгоритмах сложения двух <tex>p</tex>-битных чисел, описанных выше, можно предложить алгоритмы суммирования разложений. В этой статье их будет предложено два: $\mathrm {ExpansionSum}$ и $\mathrm {FastExpansionSum}$. Первый алгоритм прибавляет к $m$-элементному разложению $n$-элементное разложение за время <tex>O(mn)</tex>, в то время, как последний алгоритм делает это за <tex>O(n + m)</tex>.
Несмотря на такое различие в асимптотике, первый алгоритм на практике может оказаться быстрее на разложениях, чей размер мал и фиксирован, потому что программные циклы могут быть полностью развернуты, а косвенные расходы времени исчезают, так как можно отказаться от использования массива). Линейный же алгоритм имеет определенные условия, при которых подобные оптимизации невозможны.
