Одна из серьезных проблем работы с десятичными числами, представленными в двоичном коде, является проблема округления двоичного числа до значения представимого десятичного числа, ближайшего к правильно округленному десятичному числу. Ниже мы обсуждаем эту проблему и даем простой алгоритм правильного округления. Работа алгоритма проиллюстрирована тестовой программой на 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;
— двоичное число в формате 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 — целое десятичное число с N значащими цифрами;
— число xr, которое равно представимому числу, ближайшему к нормализованному двоичному эквиваленту числа X.
На скриншоте:
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++.
В программе используется довольно дорогая функция pow(10,k). Но, поскольку количество значений k невелико, вполне можно задействовать таблицу, заранее вычисленных значений 10^k, или лучше 5^k.
Напомним, что представимым десятичным числом является число, значение которого может быть точно представлено двоичным кодом. Так, число 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;
— двоичное число в формате 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 — целое десятичное число с N значащими цифрами;
— число xr, которое равно представимому числу, ближайшему к нормализованному двоичному эквиваленту числа X.
На скриншоте:
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 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.