Adaptive precision arithmetic

Эта статья находится в разработке!

Мотивация

Все вычисления, производимые компьютером во floating-point[1] модели, имеют погрешность. При большом количестве арифметических действий она возрастает. Во многих случаях результирующая погрешность уже не устраивает, и требуется либо абсолютно точное вычисление, либо меньшая погрешность. Одним из решений данной проблемы является хранение чисел в виде рациональных дробей, в которых числитель и знаменатель представляется в виде длинного целого числа. Но работать с такими числами довольно "дорого" по времени и тяжело в реализации: необходимо писать факторизацию чисел, эффективно сокращать дроби. Для улучшения работы нужны определенные оптимизации. Одной из них и является использование adaptive precision arithmetic.

Background

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

Числа с плавающей точкой, как правило, нормализованы, то есть если число не равно нулю, то первый значимый бит равен единице, а экспонента устанавливается соответственно. Например, в [math]p[/math]-битной арифметике число 1101 (десятичное 13) будет выглядеть как [math]1.101 \times 2^3[/math].

Базовые понятия

Расширения

Определение:

Два числа [math]x[/math] и [math]y[/math] называются неперекрывающимися (англ. nonoverlapping), если номер наименьшего значимого бита числа [math]x[/math] (нумерация справа налево) больше, чем номер наибольшего значимого бита числа [math]y[/math], или наоборот.

Более формально, [math]x[/math] и [math]y[/math] не перекрываются, если существует такое целое число [math]r[/math] и [math]s[/math], что [math]x = r2^s[/math] и [math]|y| \lt 2^s[/math], или [math]y = r2^s[/math] и [math]|x| \lt 2^s[/math].

Ноль не пересекается ни с одним другим числом.

Например, числа 1100 и -10.1 не пересекаются, а 101 и 10 - пересекаются.

Иногда для использовании точной арифметики может понадобиться больше, чем [math]p[/math] бит для хранения величин. В связи с этим вводится одно из базовых форм хранения чисел для такой арифметики.

Определение:

Расширением числа [math]x[/math] называется такое его представление [math]x = x_n + x_{n-1} + \dots + x_1[/math], где каждое [math]x_i[/math] выражено [math]p[/math]-битным числом с плавающей точкой и называется компонентой этого расширения.

Определение:

Расширение называется неперекрывающимся, если все его компоненты взаимно не перекрываются.

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

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

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