Изменения

<wikitex>Все вычисления, производимые компьютером во $\mathrm {floating}$ $\mathrm {point}$[http://en.wikipedia.org/wiki/Floating_point] в моделис ''плавающей точкой'', имеют погрешность. При большом количестве арифметических действий она возрастает. Во многих случаях результирующая погрешность уже не устраивает, и требуется либо абсолютно точное вычисление, либо меньшая погрешность. Одним из решений данной проблемы является хранение чисел в виде рациональных дробей, в которых числитель и знаменатель представляется в виде длинного целого числа. Но работать с такими числами довольно "дорого" по времени и тяжело в реализации: необходимо писать факторизацию чисел, эффективно сокращать дроби. Для улучшения работы нужны определенные оптимизации. Одной из них и является использование ''адаптивной арифметики'' (англ. ''adaptive precision arithmetic'').</wikitex>

==BackgroundБазовые понятия=====Представление чисел===Большинство современных процессоров поддерживают числа с плавающей точкой в форме <tex> \pm \mathrm{significand } \times 2^{\mathrm{exponent}}</tex>. Значащая часть числа (мантисса) представляет собой <tex>p</tex>-битное двоичное число в форме <tex>b.bbb \dots</tex>, где каждое <tex>b</tex>

'''Например''', числа <tex>1100</tex> и <tex>-10.1</tex> не пересекаются, а <tex>110</tex> и <tex>10</tex> {{---}} пересекаются.

'''Например''', числа <tex>1100</tex> и <tex>11</tex> {{---}} смежные, а <tex>1100</tex> и <tex>1000</tex> {{---}} нет.

Как правило, разложения должны быть неперекрывающимися, а их компоненты должны быть упорядочены от большей к меньшей по величине (то есть <tex>x_n</tex> {{- --}} большая). Далее будут рассматриваться именно такая их форма.

<wikitex>Стоит отметить, что число может быть представлено несколькими возможными неперекрывающимися разложениями: $1100 + -10.1 = 1001 + 0.1 = 1000 + 1 + 0.1$.

'''Точное округление''' (англ. ''exact rounding'') {{- --}} такой вид округления, что:

'''Например''', в 4-битной арифметике произведение <tex>111 \times 101 = 100011</tex> будет округлено в <tex>1.001 \times 2^5</tex>.

'''Округление до ближайшего четного''' (англ. ''round-to-even'') {{- --}} правило, при котором округление в вышеописанном случае производится к ближайшему <tex>p</tex>-битному четному значению.

'''Округление к нулю''' (англ. ''round-toward-zero'') {{- --}} правило, при котором округление в вышеописанном случае производится <tex>p</tex>-битному значению, находящемуся между точным значением и нулем, а также ближайшему к точному значению.

'''Например''', в 4-битной арифметике число <tex>10011</tex> будет округлено до <tex>1.010 \times 2^4</tex> по первому правилу, и до <tex>1.001 \times 2^4</tex> по второму.

При анализе округления часто используют так называемый <tex>\operatorname{ulp}</tex>.

'''ULP''' (англ. ''units in the last place'') {{- --}} эффективная величина самого младшего (<tex>p</tex>-ого) бита.

'''Например''', <tex>\operatorname{ulp}(-1100) = 1, \operatorname{ulp}(1) = 0.001</tex> в <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>.

<wikitex>Проблема с использованием этой процедуры заключается в требовании <tex>|a| \geqslant |b|</tex>. Если это заранее не известно, то необходимо выполнить сравнение перед ее вызовом. В большинстве С компиляторов, возможно, самым быстрым переносимым способом реализовать эту проверку является выражение <tex>if ((a > b) == (a > -b))</tex>. На эту проверку уйдет некоторое время, но увеличение времени может быть на удивление большим из-за современных процессоров с суперскалярными и конвейерными архитектурами, в которых вызов условного оператора может сбросить ветку предсказаний.

Пусть <tex>a</tex> и <tex>b</tex> есть <tex>p</tex>-битные числа, причем <tex>p > 3</tex>. Тогда следующий алгоритм вернет неперекрывающееся разложение <tex>x + y</tex> такое, что <tex>a + b = x + y</tex>, где <tex>x</tex> {{- --}} приближение (аппроксимация) суммы <tex>a + b</tex>, а <tex>y</tex> представляет собой ошибку округления при вычислении <tex>x</tex>.

<wikitex>Пример работы последнего алгоритма, когда $|a| < |b|$ и $|a| < |x|$. Сумма $11.11 + 1101$ будет представлена в виде разложение $10000 + 0.11$.

Пусть $x$ и $y$ {{--- }} величины, возращенные алгоритмом $\mathrm {FastTwoSum}$ или $\mathrm {TwoSum}$. На машине с округлением до ближайшего четного $x$ и $y$ {{--- }} несмежные.

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

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

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

====Grow expansionСумма разложения и числа====<wikitex>{{Теорема

Пусть $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$ также отсортированы в возрастающем порядке и не равны нулю. Алгоритм также сохраняет свойство несмежности/неперекрываемости.

====Expansion sumПростое суммирование====<wikitex>{{Теорема

====Fast expansion sumБыстрое суммирование====<wikitex>В отличие от $\mathrm {ExpansionSum}$, $\mathrm {FastExpansionSum}$ не сохраняет свойства неперекрываемости и несмежности, но гарантирует, что если если входное разложение было ''строго неперекрывающимся'', то на выходе получится разложение с таким же свойством.

'''Например''', $11000 + 11$ и $10000 + 1000 + 10 + 1$ {{--- }} строго неперекрывающиеся разложения, а $11100 + 11$ и $100 + 10 + 1$ {{--- }} нет.

Пусть $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$ также отсортированы в возрастающем порядке и не равны нулю. Алгоритм также сохраняет свойство несмежности/неперекрываемости.