419
правок
Изменения
Нет описания правки
==Мотивация==
==BackgroundБазовые понятия=====Представление чисел===Большинство современных процессоров поддерживают числа с плавающей точкой в форме <tex> \pm \mathrm{significand } \times 2^{\mathrm{exponent}}</tex>. Значащая часть числа (мантисса) представляет собой <tex>p</tex>-битное двоичное число в форме <tex>b.bbb \dots</tex>, где каждое <tex>b</tex>
обозначает один бит. Также имеется один бит на знак.
Далее в этой статье фраза "что-либо представимо в <tex>p</tex> битах" будет означать представимость в <tex>p</tex> битах мантиссы, ''не'' учитывая знак и экспоненту.
===Разложения===
{{Определение
Как правило, разложения должны быть неперекрывающимися, а их компоненты должны быть упорядочены от большей к меньшей по величине (то есть <tex>x_n</tex> {{---}} большая). Далее будут рассматриваться именно такая их форма.
<wikitex>Стоит отметить, что число может быть представлено несколькими возможными неперекрывающимися разложениями: $1100 + -10.1 = 1001 + 0.1 = 1000 + 1 + 0.1$.
</wikitex>
Неперекрывающиеся разложения нужны, например, для того, чтобы быстро вычислять знак выражения (смотрим знак большей по размеру компоненты), или для грубой оценки значения всего разложения (берем большую по величине компоненту).
}}
При вычислении результата может возникнуть ситуация, когда значение попадает в точности между двумя соседними <tex>p</tex>-битными значениями. Тогда требуется определить правило поведения в таком случае. Рассмотрим некоторые из них.
}}
Стоит отметить, что стандарт IEEE 754 использует округление до ближайшего четного по умолчанию.
Из-за округления данные операции теряют некоторые важные свойства, например, ассоциативность: <tex>(1000 \oplus 0.011) \oplus 0.011 = 1000</tex>, но <tex>1000 \oplus(0.011 \oplus 0.011) = 1001</tex>.
При анализе округления часто используют так называемый <tex>\operatorname{ulp}</tex>.
{{Определение
|definition=
'''ULP''' (англ. ''units in the last place'') {{---}} эффективная величина самого младшего (<tex>p</tex>-ого) бита.
}}
Так же полезной нотацией является <tex> \operatorname{err}(a \circledast b) </tex>, которая обозначает ошибку округлении результата выполнения операции <tex>\circledast</tex>. Отметим, что если <tex>\operatorname{ulp}</tex> всегда беззнаковая величина, то <tex>\operatorname{err}</tex> может иметь знак. Для базовых операций (сложение, вычитание, умножение) <tex> a \circledast b = a \ast b + \operatorname{err}(a \circledast b)</tex>, и точное округление гарантирует, что <tex> |\operatorname{err}(a \circledast b)| \leqslant \frac{1}{2}\operatorname{ulp}(a \circledast b)</tex>.
==Свойства==
Ошибка округления <tex>err(a \oplus b)</tex> может быть представлена в <tex>p</tex> битах.
}}
<br clear="all" />
<wikitex>Проблема с использованием этой процедуры заключается в требовании <tex>|a| \geqslant |b|</tex>. Если это заранее не известно, то необходимо выполнить сравнение перед ее вызовом. В большинстве С компиляторов, возможно, самым быстрым переносимым способом реализовать эту проверку является выражение <tex>if ((a > b) == (a > -b))</tex>. На эту проверку уйдет некоторое время, но увеличение времени может быть на удивление большим из-за современных процессоров с суперскалярными и конвейерными архитектурами, в которых вызов условного оператора может сбросить ветку предсказаний.
Это объяснение лишь гипотетическое и зависит от машины, но алгоритм $\mathrm {TwoSum}$, что будет описан ниже, избегает этого сравнения посредством трех дополнительных операций, что обычно на практике даже быстрее. Конечно же, $\mathrm {FastTwoSum}$ все же быстрее, если результат сравнения известен ''априори''.
</wikitex>
<tex>7</tex> <tex>return (x, y)</tex>
<wikitex>Пример работы последнего алгоритма, когда $|a| < |b|$ и $|a| < |x|$. Сумма $11.11 + 1101$ будет представлена в виде разложение $10000 + 0.11$.
[[Файл:Adaptive_10.jpg|слева]]
<br clear="all" />
===Суммирование разложений===
<wikitex>Базируясь на алгоритмах сложения двух <tex>p</tex>-битных чисел, описанных выше, можно предложить алгоритмы суммирования разложений. В этой статье их будет предложено два: $\mathrm {ExpansionSum}$ и $\mathrm {FastExpansionSum}$. Первый алгоритм прибавляет к $m$-элементному разложению $n$-элементное разложение за время <tex>O(mn)</tex>, в то время, как последний алгоритм делает это за <tex>O(n + m)</tex>.
Несмотря на такое различие в асимптотике, первый алгоритм на практике может оказаться быстрее на разложениях, чей размер мал и фиксирован, потому что программные циклы могут быть полностью развернуты, а косвенные расходы времени исчезают, так как можно отказаться от использования массива). Линейный же алгоритм имеет определенные условия, при которых подобные оптимизации невозможны.
Перед описанием алгоритмов суммирования разложений, приведем алгоритм прибавления к разложению <tex>p</tex>-битного числа.
====Grow expansionСумма разложения и числа====<wikitex>{{Теорема
|statement=
Пусть $e = \sum^{m}_{i=1}e_i$ - неперекрывающееся $m$-компонентное разложение; $b$ - $p$-битное число, где $p \geqslant 3$. Предполагается, что $e_1, e_2, \dots, e_m$ отсортированы в '''возрастающем''' порядке, причем все компоненты ненулевые. Тогда следующий алгоритм вернет такое разложение $h$, что $h = \sum^{m + 1}_{i=1}h_i = e + b$, где компоненты $h$ также отсортированы в возрастающем порядке и не равны нулю. Алгоритм также сохраняет свойство несмежности / неперекрываемости.
</wikitex>
====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$ также отсортированы в возрастающем порядке и не равны нулю. Алгоритм также сохраняет свойство несмежности/неперекрываемости.
<br clear="all" />
====Fast expansion sumБыстрое суммирование====<wikitex>В отличие от $\mathrm {ExpansionSum}$, $\mathrm {FastExpansionSum}$ не сохраняет свойства неперекрываемости и несмежности, но гарантирует, что если если входное разложение было ''строго неперекрывающимся'', то на выходе получится разложение с таким же свойством.
{{Определение
* [http://en.wikipedia.org/wiki/Rounding Rounding]
* [http://www.google.ru/url?sa=t&rct=j&q=Adaptive%2Bprecision%2Barithmetic&source=web&cd=4&ved=0CDgQFjAD&url=http%3A%2F%2Fwww.cs.berkeley.edu%2F~jrs%2Fpapers%2Frobustr.pdf&ei=fZigTp6xHoWa-waGxKSOBQ&usg=AFQjCNGl9T4V-Y02Wi99TjgSDLFotO5xeg&sig2=pQ5SPC_lRGCtwoBZhMhGhA Jonathan Richard Shewchuk, "Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates"]
[[Категория: Вычислительная геометрия]]