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

0

Одна из серьезных проблем работы с десятичными числами, представленными в двоичном коде, является проблема округления двоичного числа до значения представимого десятичного числа, ближайшего к правильно округленному десятичному числу. Ниже мы обсуждаем эту проблему и даем простой алгоритм правильного округления. Работа алгоритма проиллюстрирована тестовой программой на C++.
Напомним, что представимым десятичным числом является число, значение которого может быть точно представлено двоичным кодом. Так, число 0.125 точно равно двоичному числу 0.001. Можно также утверждать, что значение любого двоичного числа y равно некоторому представимому десятичному числу x. Например, значение двоичного числа y=1.001101*2^-3 равно значению десятичного представимого числа x= 0.150390625.
Будем говорить, что двоичное число y эквивалентно десятичному числу x. И наоборот, десятичное число 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++ есть функция q=frexp (x, &e), позволяющая в двоичном числе, представленном в виде 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, равное числу, округленному до N значащих цифр, надо 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.301.

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

В результате мы получаем следующий простой алгоритм правильного десятичного округления двоичных вещественных чисел. Алгоритм пригоден для любого формата двоичных чисел с произвольно заданной точностью десятичного округления N.
На входе:
-Точность десятичного округления N;
— точность представления двоичного числа p;
— двоичное число в формате 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++.

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

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

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

#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
using namespace std; int main()
{ double q,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'; q=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.

You might also like More from author