Это довольно нетривиальная задача.Лучший из известных мне подходов, который дает надежные результаты для любых двух чисел с плавающей запятой, - это использование непрерывных дробей .
. Сначала разделите два числа, чтобы получить соотношение с плавающей запятой.Затем запустите алгоритм продолжения дроби, пока он не завершится.Если оно не завершается, то оно нерационально и решения не существует.
Если оно завершается, оцените полученную непрерывную дробь обратно в одну дробь, и это будет ответом.
OfКонечно, нет надежного способа определить, есть ли решение или нет, так как это становится проблемой остановки.Но для целей с плавающей точкой ограниченной точности, если последовательность не заканчивается разумным количеством шагов, то предположим, что ответа нет.
РЕДАКТИРОВАТЬ 2: Вот обновление моего исходного решенияв C ++.Эта версия намного более надежна и, кажется, работает с любым положительным числом с плавающей запятой, за исключением INF, NAN, или чрезвычайно большими или маленькими значениями, которые переполняют целое число.
typedef unsigned long long uint64;
struct Fraction{
uint64 num;
uint64 den;
double val;
};
Fraction build_fraction(vector<uint64> &cf){
uint64 term = cf.size();
uint64 num = cf[--term];
uint64 den = 1;
while (term-- > 0){
uint64 tmp = cf[term];
uint64 new_num = tmp * num + den;
uint64 new_den = num;
num = new_num;
den = new_den;
}
Fraction f;
f.num = num;
f.den = den;
f.val = (double)num / den;
return f;
}
void get_fraction(double x){
printf("x = %0.16f\n",x);
// Generate Continued Fraction
cout << "Continued Fraction: ";
double t = abs(x);
double old_error = x;
vector<uint64> cf;
Fraction f;
do{
// Get next term.
uint64 tmp = (uint64)t;
cf.push_back(tmp);
// Build the current convergent
f = build_fraction(cf);
// Check error
double new_error = abs(f.val - x);
if (tmp != 0 && new_error >= old_error){
// New error is bigger than old error.
// This means that the precision limit has been reached.
// Pop this (useless) term and break out.
cf.pop_back();
f = build_fraction(cf);
break;
}
old_error = new_error;
cout << tmp << ", ";
// Error is zero. Break out.
if (new_error == 0)
break;
t -= tmp;
t = 1/t;
}while (cf.size() < 39); // At most 39 terms are needed for double-precision.
cout << endl << endl;
// Print Results
cout << "The fraction is: " << f.num << " / " << f.den << endl;
printf("Target x = %0.16f\n",x);
printf("Fraction = %0.16f\n",f.val);
cout << "Relative error is: " << abs(f.val - x) / x << endl << endl;
cout << endl;
}
int main(){
get_fraction(15.38 / 12.3);
get_fraction(0.3333333333333333333); // 1 / 3
get_fraction(0.4184397163120567376); // 59 / 141
get_fraction(0.8323518818409020299); // 1513686 / 1818565
get_fraction(3.1415926535897932385); // pi
system("pause");
}
Вывод:
x = 1.2504065040650407
Continued Fraction: 1, 3, 1, 152, 1,
The fraction is: 769 / 615
Target x = 1.2504065040650407
Fraction = 1.2504065040650407
Relative error is: 0
x = 0.3333333333333333
Continued Fraction: 0, 3,
The fraction is: 1 / 3
Target x = 0.3333333333333333
Fraction = 0.3333333333333333
Relative error is: 0
x = 0.4184397163120567
Continued Fraction: 0, 2, 2, 1, 1, 3, 3,
The fraction is: 59 / 141
Target x = 0.4184397163120567
Fraction = 0.4184397163120567
Relative error is: 0
x = 0.8323518818409020
Continued Fraction: 0, 1, 4, 1, 27, 2, 7, 1, 2, 13, 3, 5,
The fraction is: 1513686 / 1818565
Target x = 0.8323518818409020
Fraction = 0.8323518818409020
Relative error is: 0
x = 3.1415926535897931
Continued Fraction: 3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 3,
The fraction is: 245850922 / 78256779
Target x = 3.1415926535897931
Fraction = 3.1415926535897931
Relative error is: 0
Press any key to continue . . .
Здесь следует отметить, что он дает 245850922 / 78256779 для pi.Очевидно, пи иррационально .Но насколько позволяет двойная точность, 245850922 / 78256779 ничем не отличается от pi.
В принципе, любая дробь с 8 - 9 цифрами в числителе / знаменателе имеет достаточно энтропии, чтобы охватить почти все DPзначения с плавающей запятой (исключая угловые регистры, такие как INF, NAN или очень большие / маленькие значения).