Правильное округление десятичных чисел в двоичном коде

Одна из серьезных проблем работы с десятичными числами, представленными в двоичном коде, является проблема округления двоичного числа до значения представимого десятичного числа, ближайшего к правильно округленному десятичному числу. Многие, даже опытные программисты, не осознают важность этой проблемы, полагая, что работая в формате double, они гарантированны от всяких сюрпризов.  И что задача округления возникает только на этапе вывода результата на консоль. Но это ни так. Мы покажем на примерах, что игнорирование процедуры округления значительно снижает точность расчетов для двоичных чисел с плавающей точкой. Ниже мы обсуждаем эту проблему и даем простой алгоритм правильного округления. Работа алгоритма проиллюстрирована тестовой программой на C++.

Представим себе некий КАЛЬКУЛЯТОР — этакий черный ящик. В него мы посылаем числа, выбрав  предварительно операцию — сложение, вычитание, умножение, деление или др. Возвращает он нам результат вычисления. Нам ничего не известно, о том, как он выполняет вычисления. Чтобы убедиться, что калькулятор работает правильно, мы результат  должны сравнить с эталоном. За эталон мы берем число, в правильности которого мы уверены. Как правило, это число, которое мы можем проверить, вычислив, например, вручную на бумаге. Если возвращаемые числа с калькулятора  совпадают с эталоном, все нормально, мы доверяем калькулятору. А если не совпадают? Тогда есть два варианта, либо взять другой, проверенный калькулятор, или, если по каким-то причинам этого сделать нельзя, попытаться  понять, какие есть  ограничения для чисел, которые можно    использовать, чтобы получить результат максимально близкий к эталонному. В случае, когда мы на вход калькулятора подаем десятичные операнды и калькулятор десятичный, единственное ограничение — это число не должно превышать разрядную сетку калькулятора. Если калькулятор двоичный, то для большинства десятичных чисел ограничений возникает много. На выход такого калькулятора возвращаются, как правило, представимые в двоичной системе числа, которые в той или иной мере аппроксимируют точный десятичный ответ, который, в свою очередь,  как правило, является непредставимым числом.

Напомним, что представимым десятичным числом является число, значение которого может быть точно представлено двоичным кодом. Так, число 0.125 точно равно двоичному числу 0.001. Можно также утверждать, что значение любого двоичного числа y равно некоторому представимому десятичному числу x. Например, значение двоичного числа y=1.001101*2^-3 равно значению десятичного представимого числа x= 0.150390625.
Будем говорить, что двоичное число y эквивалентно десятичному числу x, и наоборот, десятичное число x эквивалентно двоичному числу y, если значения x и y совпадают.

Давайте посмотрим, что происходит с десятичным числом, когда оно вводится с консоли, или, когда оно встречается в программе в качестве константы.
Любое десятичное число компилятором преобразуется (конвертируется) в заданный программистом формат. Поскольку быстрее всего в компьютере обрабатываются двоичные числа, то входное десятичное число преобразуется, чаще всего, либо в формат с фиксированной точкой (в том числе в int), либо в один из форматов с плавающей точкой — single, double, или в другой двоичный формат.

Согласно стандарту IEEE754, вещественные числа во внутреннем формате машины представляются в нормализованном двоичном виде. Так, двоичное положительное вещественное число y можно представить как y=b0.b1…bp*2^e (b0≠0).
Это же число можно представить как 0.b0b1…bp*2^(e+1) (b0≠0), если e+1>0 и 0.b0b1…bp*2^e (b0≠0), если e<0.
Далее мы будем придерживаться второго представления, т.к. в нашей, приведенной ниже, тестовой программе на C++ есть функция frexp (), позволяющая в двоичном числе, представленном в виде b0.b1…bp*2^e, определить значение экспоненты e.

Итак, десятичный эквивалент любого двоичного нормализованного числа y =0.b0b1…bp*2^e (b0≠0) равен некоторому нормализованному десятичному числу x=0.d0d1…dN…dn*10^E (d0≠0).
Например, число y=0.1001101*2^-2 эквивалентно представимому десятичному числу x=0.150390625.
Чтобы из x получить число Xr, равное числу, округленному до значащих цифр, надо X умножить на коэффициент 10^k, где k=N-E. Это нужно для того, чтобы полученное число содержало целую часть с N значащими цифрами, которое затем можно было округлить до ближайшего целого. Округленное целое число затем надо привести к прежнему масштабу, умножив его на 10^-k. Математически это можно записать следующей формулой:
X=[x*10^k+0.5]*10^-k=[y*10^k+0.5]*10^-k, где []-целая часть числа.

Можно показать, что целое двоичное число B, содержащее m двоичных цифр, равно значению десятичного числа D, которое содержит n=⌊m*log2⌋ десятичных разрядов, при условии, что B < 10^n. И равно n=n+1, при условии, что B ≥ 10^n. В расчетах можно принять log2≈0.3.

Определим значение k на основе информации, имеющейся в двоичном представлении числа y. В формуле k=N-E точность округления N известна, поэтому надо определить экспоненту E.
Экспоненту E определим из соотношения: E=⌊e*0.3⌋.
Осталось учесть следующее обстоятельство. Если x*10^k= X >10^N, то его нужно умножить на 10^(-1) и скорректировать коэффициент k. Получим X=X*10^(-1), k=k-1.
Округленное число будет равно Xr=X*10^(-k).

В результате мы получаем следующий простой алгоритм правильного десятичного округления двоичных вещественных чисел. Алгоритм пригоден для любого формата двоичных чисел с произвольно заданной точностью десятичного округления N.
На входе:
-Точность десятичного округления N;
— двоичное число в формате y= 0.b0b1…bp*2^e (b0≠0).
На выходе: Округленное десятичное число X=0.d0d1…dN*10^E.
— 1. Определить экспоненту e двоичного числа y;
2. E=⌊e*0.3⌋;
3. k=N-E;
4. X=x*10^k;
5. Если X<10^N, то п.8;
6. X=X*10^-1;
7. k=k-1;
8. xr=[X+0.5]*10^(-k);
End.
— В приведенном алгоритме число xr представляет собой представимое десятичное число ближайшее к числу, которое является правильным округлением числа x, которое в свою очередь является десятичным эквивалентом числа y.
Поскольку мы привыкли работать с десятичными числами, то, как правило, входной поток представляет собой именно десятичные числа. На выходе мы хотим получить тоже десятичные числа. Например, как в Excel. Но, после конвертации десятичных чисел в двоичный код, они, как правило, необратимо трансформируются. В результате этого, округленные числа, полученные из преобразованных в двоичный код чисел, могут не совпадать с правильным округлением чисел, напечатанным на консоле. Это касается, прежде всего, случаев, когда мы пытаемся округлить десятичное число до максимально возможного количества значащих цифр. Для single, это 7, а для double — 15.
Это хорошо можно исследовать на тестовой программе ниже, которую автор написал на C++.

В тестовой программе, по запросу, на консоль вводится:
-точность N десятичного округления числа X, которое является ближайшим представимым числом двоичного эквивалента числа x;
— число x в произвольной форме.

Под введенным произвольным десятичным числом x печатается число X, которое является ближайшим к x представимым числом (см. скриншот ниже).
Округление выполняется над числом X, т.к. точное значение числа x утеряно при двоичной конвертации.
Возвращается:
— десятичное число в формате Xr =M*10^(N+e), где M — целое десятичное число с значащими цифрами;
— число xr, которое равно представимому числу, ближайшему к нормализованному двоичному эквиваленту числа X.
image
На скриншоте:

N=15 — количество десятичных значащих цифр, до которого округляется входное десятичное число.
x=7.123456789098765321 e-89 — десятичное число, которое мы хотели бы округлить до 15 значащих цифр.
X=7.12345678909876559 e-089 — представимое десятичное число, значение которого равно двоичному числу, которое получено в результате конвертации числа x в формат p=53.
Xr= x=712345678909877e-103 — число с целочисленной мантиссой, полученное в результате округления числа X.
xr= x=7.12345678909877e-089 — число, полученное в результате нормализации двоичного эквивалента десятичного числа Xr. Оно является ближайшим к Xr.

Ниже приводится код тестовой программы правильного округления десятичных чисел, представляемых в двоичном коде, на C++.

#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
using namespace std;

int main()
{
   double x,xr,X;
   unsigned long long int Xr;
   int N,p,E,e,k;

  cout <<"Input a binary precision p=";
  cin>>p;
  cout <<"Input a decimal precision N=";
  cin>>N;
  cout <<endl<<"Input a number and press ENTER:"<<"\n"<<"x= ";
  cin>>x;
   cout<<"X= "<< setprecision(18)<<x << '\n';

    frexp (x, &e);
    E =static_cast <int> (e*0.301);
    k=N-E;
   if (E<0)       //for format xr=d0.d1...dN*10^E (d0≠0).
        k=k+1;
    X=x*pow(10,k);
       if (X > pow (10,N)){
            X=X/10;
            k=k-1;
      }

       X=X+0.5;
       Xr=static_cast <unsigned long long int> (X);
       xr=Xr*pow(10,-k);

    cout<<endl <<"Xr= "<<Xr<<"e"<<-k<<'\n';
    cout<<"xr="<<xr<<'\n';

   system("pause");
      return 0;
}

В программе используется довольно дорогая функция pow(10,k). Но, поскольку количество значений k невелико, вполне можно задействовать таблицу, заранее вычисленных значений 10^k, или лучше 5^k.

В заключение отметим, что при исследовании работы тестовой программы можно столкнуться с таким феноменом. Если мы округляем некоторое десятичное число x до N значащих цифр и (N+1)-ая цифра округляемого числа равна 5, например,   x=1.c0c1…cN 5, то в одних случаях, округление выполняется до  x=1.c0,c1…cN, а в других до x=1.c0,c1…cN+1ulp. Это не является ошибкой программы. Это ошибка компилятора, или, по крайней мере,  некоторых компиляторов C++. Хотя, не исключено, что это особенность работы процессора. Так, число x=1.45, после конвертации   в формат double, должно принять десятичное значение 1.44999999999999995559107901499. И его правильное округление до 2 значащих цифр должно вернуть результата 1.4. Однако, компилятор округляет это число до 1.5 и дальнейшее округление до ближайшего возвращает  число 1.5.

Я изобретатель, имею18 авторских свидетельств СССР на изобретения

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *