15.2. Сравнение чисел с плавающей точкой с использованием целых операций

Одним из достоинств ЮЕЕЕ-кодирования чисел с плавающей точкой является то, что все не NaN-значения корректно упорядочены, если рассматривать их как знаковые целые числа.

Для того чтобы запрограммировать сравнение чисел с плавающей точкой с использованием целых операций, необходимо отказаться от результата сравнения "неупорядоче-но". В ШЕЕ 754 такой результат получается в том случае, если один или оба аргумента оператора сравнения представляют собой значение NaN. Описываемый далее метод трактует значения NaN как числа, превыщающие бесконечное значение.

Сравнение становится существенно проще, если считать, что величина -0.0 строго меньше +0.0 (что не согласуется со стандартом IEEE 754). Считая описанные допущения

приемлемыми и используя для сравнений с плавающей точкой обозначения <, < и =, а символ = - как напоминание о том, что приведенные формулы не совсем корректно работают со значениями +0.0, можно использовать следующие формулы:

a=b = {a=b),

a<b

a<b«

aO&a<b

аО&айЬ

a<0&a>b

<0&a>A

Если же значение -0.0 в обязательном порядке должно быть равно значению +0.0, то приведенные формулы существенно усложняются (хотя и не настолько, как могло бы показаться необходимым на первый взгляд).

a=b = {a=b)\{-a=a&.-b=b) = (в = А) I ((а I А) = 0x80000000) = {а=Ь)\({(а IА)&OxTFFFFFFF) = О)

а<Ь

ff \ f и

aSO&a<A I а<й&а>Ь

а<Ь =

а>0&а<Ь

f и

а<0&а>А

(а\Ь \[[а\ь] =

/0x80000000

0x80000000

В некоторых приложениях более эффективным может оказаться путь, состоящий в некотором преобразовании чисел и последующем сравнении с плавающей точкой с использованием единственной команды. Например, при сортировке и чисел преобразование придется выполнить для каждого числа только один раз, в то время как количество сравнений составляет, как минимум, \п log п \ (в смысле минимакса).

В табл. 15.2 приведены четыре типа таких преобразований. Для преобразований в левом столбце -0.0 эквивалентно +0.0, в правом - значение -0.0 < +0.0. В любом случае смысл сравнения при преобразовании не изменяется. Переменная п - знаковая, t - беззнаковая, а с может быть как знаковой, так и беззнаковой.

Таблица 15.2. Подготовка чисел с плавающей точкой к целым сравнениям

-0.0 = +0.0 (IEEE)

-0.0 < +0.0 (He-IEEE)

n+Oxeooooooo;

if (n >= 0) n else n = -n;

Используется беззнаковое сравнение

с = 0X7FFFFFFF;

if (n < 0) n = (n * с) + 1;

Используется знаковое сравнение

с = 0x80000000;

if (n < 0) n = с - n;

Используется знаковое сравнение

t = n >> 31;

n = (n * (t >> 1)) - t;

Используется знаковое сравнение

if (n >= 0) n = п+ОХ80000000; else n = -n;

Используется беззнаковое сравнение

с = 0X7FFFFFFF;

if (n < 0) n = n * c;

Используется знаковое сравнение

с = 0X7FFFFFFF;

if (n < 0) n = с - п;

Используется знаковое сравнение

t = (unsigned)(n>>30) >> 1; n = n * t;

Используется знаковое сравнение

В последней строке приведен код без ветвлений, который может быть реализован на RISC-компьютере с базовым набором команд, с использованием четырех команд в левом столбце, и трех - в правом (эти команды должны быть выполнены для каждого из аргументов операции сравнения).

15.3. Распределение ведущих цифр

Когда IBM выпустила в 1964 году свою ЭВМ Systeni/360, все были озабочены снижением точности арифметики с плавающей точкой. Предыдущая линия ЭВМ, семейство 704-709-7090, имела 36-битовое слово. Представление числа с плавающей точкой с одинарной точностью состояло из 9-битового поля знака и показателя степени, за которым следовали 27 бит двоичного представления дроби. Старший бит дроби явно включался в это представление числа, так что точность представления чисел с плавающей точкой была равна 27 битам.

ЭВМ Systeni/360 имела 32-битовое слово. Для хранения чисел с плавающей точкой одинарной точности IBM был выбран формат с 8-битовым полем знака и показателя степени и 24-битовым полем дробной части. Это снижало точность представления с 27 до 24 бит, что само по себе достаточно плохо, но на самом деле все обстояло еще хуже. Для того чтобы обеспечить большой диапазон показателя степени, каждая единица в 7-битовом показателе приравнивалась к 16. Это привело, по сути, к представлению дробной части в шестнадцатеричном виде, где первая цифра числа может принимать люг бое двоичное значение от 0001 до ПИ (от I до 15). Числа, старшая цифра которых равна I, таким образом, имели точность всего лишь 21 бит (поскольку три старших бита такого числа нулевые), и таких чисел должно быть примерно 1/15, или 6.7% от всех чисел.

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

15.3. РАСПРЕДЕЛЕНИЕ ВЕДУЩИХ ЦИФР

Рассмотрим распределение ведущих цифр у десятичных чисел. Предположим, что у нас есть большое множество чисел, представляющих различные физические величины - длины, объемы, массы и т.п., выраженные в "научной" записи (например, б.022х1(Я). Если старшая цифра у таких чисел имеет некоторое распределение, то это распределение не должно зависеть от используемых единиц измерений, например сантиметров или дюймов, фунтов или килограммов и т.д. Таким образом, если умножить все числа даьшого множества на некоторую константу, распределение старших цифр должно остаться тем же. Например, рассматривая умножение на 2, мы должны сделать вывод о том, что чисел с ведущей единицей (от 1.0 до 1.999..., умноженных на некоторую степень 10) должно быть столько же, сколько и чисел с ведущими цифрами 2 или 3 (от 2.0 до 3.999..., умноженных на некоторую степень 10), поскольку не должно иметь значения, измеряется ли длина в метрах или в полуметрах, масса - в килограммах или полукилограммах и т.п.

Пусть f{x), 1 д: < 10, - функция плотности вероятности для ведущих цифр множества чисел с физической размерностью. Эта функция обладает тем свойством, что

пропорционально количеству чисел, старшая цифра которых находится в диапазоне от а до Ь. Для малых приращений Дд: должно выполняться следующее соотношение (см. приведенный ниже рисунок):

/(1)-Дг = /(х)-хДг,

1 X х+х&х 10

поскольку /(1)Дд: примерно пропорционально количеству чисел в диапазоне от 1 до

1 + Дд; (игнорируя множитель степени 10), а f{x)-xAx приблизительно пропорционально

количеству чисел в диапазоне от д: до х + хАх. Так как последнее множество представляет собой первое, умноженное на дг, коэффициенты пропорциональности должны быть одинаковы, а следовательно, функция плотности вероятности имеет простейший вид:

/()=/(1)Л-

Поскольку площадь под кривой от д:= 1 до х= 10 должна быть равна 1 (все числа со старшими цифрами лежат в диапазоне от 1.000... до 9.999...), легко показать, что

/(1) = 1/1п10.

Числа со старшей цифрой в диапазоне от а до b {\<а<Ь<\0) составляют часть общего количества всех чисел, выражаемую формулой

хЫт !п10

\пЬ/а , b