Спецификация. Алгоритм вычисления целой части числа

Постановка задачи

Алгоритм вычисления целой части числа

Хорошо известна функция y = floor(x), вычисляющая наименьшее целое, не превосходящее вещественного аргумента x. Определим предикат:

formula flp(real x, int i) = i <= x & x < i + 1;

Спецификация функции floor представляется определением:

floor(real x: int y) post flp(x, y);

Нам требуется построить быстрый алгоритм вычисления floor для вещественных чисел в плавающем формате, определяемом в языке C++ типами float, double и quad. В алгоритме плавающие числа представлены в бинарном формате, определяемом стандартом IEEE 754. Использовалась последняя версия IEEE 754-2008 этого стандарта. Плавающее число представляется тройкой (S, E, T), где S = {0, 1} ¾ знак числа, E ¾ сдвинутая экспонента, а T ¾ мантисса в нормализованном представлении без старшего разряда (равного 1). В соответствии со стандартом, значение плавающего числа определяется по формуле:

y = (-1)^S * 2^E-bias * (1 + 2^1-p * T).

Здесь bias ¾ сдвиг экспоненты, p ¾ число битов в представлении мантиссы, 1 £ E £ 2^w - 2, w ¾ число битов в представлении экспоненты. Значение E = 0 предназначено для кодирования нулей и ненормализованных малых значений; случай E = 2^w – 1 соответствует бесконечности (положительной или отрицательной в зависимости от знака S) и числу NaN (not a number). Для формата 32 (float) значения bias = 127, w = 8 и p = 24. Для формата 64 (double) значения bias = 1023, w = 11 и p = 53.

Значение функции floor для положительной и отрицательной бесконечностей и числа NaN не определено. Для E = 0 значением функции floor является 0 при S = 0 и -1 при S = 1. Особым является случай отрицательного нуля. Если трактовать его как сверхмалое отрицательное значение, не представимое в формате ненормализованных малых значений, то значением floor должно быть -1. Однако это никак не следует из стандарта: при отрицательном переполнении (underflow) отрицательного результата нет явного требования представлять этот результат отрицательным нулем. Впрочем, в стандарте декларирован режим округления roundTowardNegative, при котором возможно получение отрицательных нулей в операциях типа x – x. В этом случае решение floor(-0) = -1 может показаться сомнительным.

В нашем алгоритме ограничимся случаем нормализованного числа при 0 < E < 2^w – 1. Однако мы не выставляем этого ограничения в предусловии. Алгоритм определен также для E = 0 и E = 2^w – 1, однако в соответствии с бинарным представлением плавающих чисел не может быть там применен.

Определим константы и типы:

constnat bias;

constsubtype (nat i: i > 0) p;

constsubtype (nat i: i >= 2) w;

constnat m = p + w; % число битов в представлении числа y.

Здесь m определяет разрядность числа, т.е. число битов в представлении плавающего числа. Значения bias, p и w представлены неинтерпретированными константами. Однако ограничения p > 0 и w >= 2 по существу используются при доказательстве корректности программы.

type bit = { nat a | a = 0 or a = 1};

type nate = { nat e | e < bias + m - 2};

type natp = { nat i | i < 2 ^ (p - 1)}

type intm = { int x | - 2^(m-1) < x & x < 2^(m-1)};

Дадим определение спецификации:

formula val(bit S, nate E, natp T: real) =

(-1)^S * 2^(E - bias) * (1 + 2^(1 - p) * T);

floor(bit S, nate E, natp T: intm y) post flp(val(S, E, T), y);

Функция val определяет вещественное значение плавающего числа в соответствии со стандартом. В спецификации предиката floor предусловие отсутствует, поскольку все ограничения на входные значения представлены описаниями типов bit, nate и natp. Тип natp определяет очевидное ограничение для мантиссы T, поскольку в соответствии со стандартом для T используется p-1 битов. Тип intm определяет естественное требование: результат функции floor должен помещаться в m битов. Тип nate вводит ограничение для значений экспоненты E. Далее будет автоматически доказано, что для указанных параметров S, E и T значение результата y будет находиться в пределах типа intm.

Дата добавления: 2015-06-27