Изменения

Базируясь на алгоритмах сложения двух <tex>p</tex>-битных чисел, описанных выше, можно предложить алгоритмы суммирования расширений. В этой статье их будет предложено тридва: ExpansionSum, LinearExpansionSum и FastExpansionSum. Первый алгоритм прибавляет к m-элементному расширению n-элементное расширение за время <tex>O(mn)</tex>, в то время, как последние два алгоритма делают последний алгоритм делает это за <tex>O(n + m)</tex>.

Несмотря на такое различие в асимптотике, первый алгоритм на практике может оказаться быстрее на расширениях, чей размер мал и фиксирован, потому что программные циклы могут быть полностью развернуты, а косвенные расходы времени исчезают, так как можно отказаться от использования массива). Линейные алгоритмы имеют Линейный же алгоритм имеет определенные условия, при которых подобные оптимизации невозможны.

ExpansionSum и LinearExpansionSum имеют имеет свойство, что если входные данные были неперекрывающимися (несмежными), то и на выходе мы получим расширения с соотв.свойством.

FastExpansionSum быстрее, чем LinearExpansionSum, используя шесть операций на компоненту вместо девяти, но имеет несколько важный серьезных недостатков.Первый из них - алгоритм не сохраняет свойств неперекрываемости/несмежности. Второй - LinearExpansionSum не полагается на правило округления в случае попадания результата между соседними <tex>p</tex>-битными числами, а FastExpansionSum алгоритм основывается на округлении до ближайшего четного, что делает его непереносимым.

Недостатком Как правило, общим недостатком алгоритмов работы с расширениями является то, что в расширении на выходе могут быть нулевые элементы, даже если в исходном расширении их не было. Например, если подать на вход расширениея 1111 + 0.0101 и 1100 + 0.11, то результатом будет 11100 + 0 + 0 + 0.0001. К счастью, алгоритмы, описанные в этой статье хорошо справляются с этой проблемой.