Оптимизация предикатной программы

Предикатная программа

Преобразуем формулу для функции val следующим образом:

val(S, E, T) = (-1)^S * 2^(E – bias – p + 1) * (2^(p-1) + T) = (-1)^S * 2^d * z,

где d = E – bias – p + 1, z = 2^(p-1) + T. При этом z >= 2^(p-1) и z < 2^p.

Определим функцию:

formula val1(bit S, nat d, z: real) = (-1)^S * 2^d * z;

Тогда вычисление функции floor можно свести к вычислению функции floor1 со спецификацией:

floor1(bit S, int d, nat z: intm y)

pre z >= 2^(p-1) & z < 2^p & d < w post flp(val1(S, d, z), y);

Таким образом получаем следующее определение предиката floor:

floor(bit S, nat E, T: intm y) pre T < 2^(p-1) & E – bias < m – 2 (1)

{ floor1(S, E – bias – p + 1, 2^(p-1) + T: y) } post flp(val(S, E, T), y);

Далее, требуемое значение функции floor получается соответствующим сдвигом натурального z. Полный алгоритм представляется следующим определением:

floor1(bit S, int d, nat z: intm y) pre z >= 2^(p-1) & z < 2^p & d < w (2)

{ if (S = 0) { if (d >= 0) y = 2^d * z else y = div(z, 2^(-d)) }

elseif (d >= 0) y = - 2^d * z

elseif (mod(z, 2^(-d)) = 0) y = - div(z, 2^(-d))

else y = - div(z, 2^(-d)) – 1

} post flp(val1(S, d, z), y);

Для отрицательных чисел алгоритм сложнее ¾ фактически реализуется функция ceiling, реализующая приведение к целому в другую сторону.

Следует отметить следующие особенности алгоритма. Результат вычисления y = 2^d * z (и y = - 2^d * z) может оказаться неточным, если неточным было исходное представление числа в плавающем формате. Причем погрешность может оказаться большой ¾ до 2^d. Из-за неточности исходного представления возможна погрешность результата y от -1 до +1 при вычислении div(z, 2^(-d)), а также ошибочность вычисления условия mod(z, 2^(-d)) = 0.

Реализуется замена конструкций программы на более эффективные эквивалентные конструкции с использованием битовых операций. В определении (1) реализуется замена 2^(p-1) + T на 2^(p-1) or T:

floor(bit S, nat E, T: intm y) pre T < 2^(p-1) & E – bias < m – 2 (3)

{ floor1(S, E – bias – p + 1, 2^(p-1) or T: y) } post flp(val(S, E, T), y);

Реализуется замена конструкций определения (2) на более эффективные эквивалентные конструкции с использованием битовых операций. Применяются следующие замены:

· z * 2^d на z << d

· div(z, 2^(-d)) на z >> (-d)

· mod(z, 2^(-d)) = 0 на z & (2^(-d) – 1) = 0.

Значение 2^(-d) – 1 состоит из (-d) единичных битов. Такое значение можно сгенерировать посредством сдвига: (2^p – 1) >> (p + d).

В соответствии со стандартом языка C++ результат операции сдвига не определен, если величина сдвига превышает длину сдвигаемого значения. Сдвиг вправо ограничен в предусловии значением w. Поэтому при замене div(z, 2^(-d)) на z >> (-d) следует отдельно рассмотреть случай –d > p, при котором div(z, 2^(-d)) = 0. Проведя указанные замены получим следующую программу:

floor1(bit S, int d, nat z: intm y) pre z >= 2^(p-1) & z < 2^p & d < w (4)

{ if (S = 0) { if (d >= 0) y = z << d elseif (–d > p) y = 0 else y = z >> (-d) }

elseif (d >= 0) y = - (z << d)

elseif (–d > p) y = - 1

elseif (z & ((2^p – 1) >> (p + d)) = 0) y = - (z >> (-d))

else y = - (z >> (-d)) – 1

} post flp(val1(S, d, z), y);

Отметим, что полученная программа по-прежнему остается предикатной, и она могла бы быть объектом доказательства корректности вместо исходной предикатной программы (1) и (2).

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