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].