Вычисления с фиксированной точкой. Основные принципы (ч.1)

В вычислительной математике дробные значения представляют в виде пары целых чисел (n, e): мантиссы и экспоненты (по-русски более верно «показателя степени», но для краткости и по привычке буду в дальнейшем употреблять именно слово «экспонента»). Пара представляет дробное число в виде n * 2 -e . Экспоненту можно рассматривать как количество цифр перед запятой, отделяющей дробную часть числа. Если экспонента переменная, записываемая в регистр и неизвестная при компиляции, (n, e) называют числом с плавающей запятой. Если экспонента известна заранее, (n, e) называют числом с фиксированной точкой. Числа с фиксированной точкой могут записываться в обыкновенные целочисленные переменные (регистры) путем сохранения только мантиссы. Экспоненту обычно обозначают буквой q. Так что, встретив в комментарии к переменной что-нибудь в духе "q15 multiplier", следует рассматривать эту переменную как число с фиксированной точкой и экспонентой, равной 15. Впрочем, я еще вернусь к вопросу нотации, встречающейся в различных исходниках и статьях.

Итак, мы разобрались с тем, что при работе с фиксированной точкой экспонента нигде не записывается и держится «в уме». Как же производить расчеты? Вычислительная арифметика — целая наука со своими формулами, аксиомами и теоремами. Целью данной статьи не было давать введение в эту науку. Подходы, приведенные ниже, в первую очередь ориентированы на программистов, решающих инженерные и прикладные задачи, т.е. такие, где диапазоны допустимых значений и необходимые точности вычислений известны и ограничены. Еще одно ограничение статьи — здесь не приводятся алгоритмы тригонометрических и прочих сложных операций. Сделать их полный обзор в одной статье нереально (и вряд ли необходимо). В статье дан базис, необходимый для понимания таких алгоритмов (и разработки собственных), — правила выполнения базовых операций (сложение/вычитание, умножение, деление) и общая методика вычислений с фиксированной точкой.

Сложение выполняется просто, если представить в уме, что мы должны сложить две десятичные дроби «в столбик» на листе бумаги. При выполнении данной операции числа записываются в столбик так, чтобы запятые, отделяющие дробную часть, располагались одна под другой. В двоичной арифметике подобная операция называется приведением экспонент. Если перейти от «бумажки» к математической записи, получится следующее: Пусть имеется два числа a = n1 * 2 -q1 и b = n2 * 2 -q2 . Тогда: a + b = n1 * 2 -q1 + n2 * 2 -q2 = (n1 + n2 * 2 (q1 — q2) )*2 -q1 . Множитель 2 (q1 — q2) при втором слагаемом по сути означает арифметический сдвиг для приведения чисел к одной экспоненте. Стоит отметить, что результат вычисления также может сдвигаться для приведения к требуемому значению экспоненты. Фрагмент кода на С:

• жертвовать точностью или нет? Можно ведь привести слагаемые к меньшей экспоненте сдвигом вправо и отбросить младшие разряды.
• ограничены ли значения переменных? Сдвиг вправо в данном случае, например, не приводит к потере точности.
• есть ли возможность расширить разрядность?

Умножение с фиксированной точкой может выполняться без хитрых выравниваний и приведения к единой экспоненте. Тем не менее умножение — достаточно опасная операция, которая чаще всего в итоге приводит к потере точности и требует особой аккуратности в обращении. Начнем с математического описания умножения: Пусть имеется два числа a = n1 * 2 -q1 и b = n2 * 2 -q2 . Тогда: a * b = n1 * 2 -q1 * n2 * 2 -q2 = n1 * n2 * 2 -(q2 + q1) . Из выражения видно, что экспоненты чисел при умножении складываются: 2 -(q2 + q1) . Разрядность данных в этой статье не рассматривается, пока достаточно лишь запомнить, что для безопасного умножения без переполнения и потери точности разрядность результата должна быть не меньше суммарной разрядности сомножителей. Из-за сложения экспонент результат умножения приходится корректировать для выполнения дальнейших вычислений. При уменьшении экспоненты младшие разряды результата отбрасываются. То есть происходит потеря точности. Можно уменьшить потери точности (и иногда приходится), но способы борьбы с потерями всегда связаны с накладными расходами. Фрагмент кода на С:

Отмечу, что 15 младших разрядов результата умножения были отброшены, чтобы привести число к формату слагаемого. Можно было, конечно, увеличить разрядность переменной c, но, как я уже говорил, на практике диапазоны значений обычно ограничены и младшими разрядами умножения зачастую пренебрегают. Кроме того, не учитывается возможность наличия в исходных сомножителях ненулевых старших разрядов. Но в данной статье обработка переполнений не рассматривается.

Начнем с математического выражения для деления: Пусть имеется два числа a = n1 * 2 -q1 и b = n2 * 2 -q2 . Тогда: a / b = n1 * 2 -q1 / (n2 * 2 -q2 ) = n1 / n2 * 2 -(q1 — q2) . Сомножитель 2 -(q1 — q2) означает, что при выполнении деления экспонента автоматически уменьшается. Если не принять меры, часть значащих разрядов отбрасывается автоматически. Способ коррекции очевиден — необходимо заранее увеличить разрядность делителя настолько, чтобы в результате деления получить желаемое количество значащих бит: a / b = n1 * 2 -q1 * 2 q3 / (n2 * 2 -q2 ) = n1 / n2 * 2 -(q1 — q2 + q3) . Таким образом, экспонента частного увеличена на q3 разряда. Фрагмент кода на С:

Очевидно, что при превышении числом разрядности 32 бита, проблему уже не решить так просто. Тем не менее, для простых инженерных расчетов 32-битных чисел обычно более, чем достаточно. Есть один простой способ значительно сократить потерю точности при делении — предварительное нормирование делимого. Нормирование — фактически максимальный сдвиг мантиссы влево, при котором не происходит отбрасывания значащих битов. Определить, на сколько можно сдвинуть число, можно путем подсчета ведущих нулей в делимом, для чего существуют специальные алгоритмы (или даже аппаратные инструкции процессора). После деления частное следует сдвинуть вправо на такое же количество бит для восстановления экспоненты. Вышеприведенный фрагмент кода при этом может выглядеть таким образом:

Как видим, потери точности в данном случае не произошло и без увеличения разрядности делимого. Впрочем, так происходит не всегда, и если требуется остаться в рамках определенной разрядности (например, 32 бита), приходится реализовывать деление алгоритмически. В обзорной статье вряд ли стоит погружаться в такие дебри — для понимания процесса деления и связанных с ним сложностей достаточно уже приведенного описания.