Я написал относительно простой код для преобразования парных чисел в рациональные числа. Код работает, и он гарантированно найдет наименьшее рациональное число для данного двойного числа; однако, это медленнее, чем патока в январе. Я провел день, пробуя различные методы, чтобы улучшить его безрезультатно. Есть идеи, как это ускорить? Фактический алгоритм находится в цикле while, и это всего лишь 8 строк.
#include <iostream>
#include <iomanip>
using namespace std;
void rationalize(double number) {
bool isNegative = false;
if (number == 0.0) {
cout << number << ": " << "0/1" << endl;
return;
}
if (abs(number) < (1.0 / (double) LONG_MAX)) {
cout << number << " is to small " << endl;
return;
}
if (abs(number) > (double)LONG_MAX) {
cout << number << " is to big " << endl;
return;
}
if (number < 0) {
isNegative = true;
number *= -1;
}
long numerator = 1; // at this point, both numerator
long denominator = 1; // and denominator must be >= 1
double diff = 1.0 - number;
//while ((abs(diff) > DBL_EPSILON) && (numerator > 0) && (denominator > 0)) {
while ((abs(diff) > FLT_MIN) && (numerator > 0) && (denominator > 0)) {
if (diff > 0) {
denominator++;
} else {
numerator++;
}
diff = ((double) numerator / (double) denominator) - number;
} // end while
if ((numerator <= 0) || (denominator <= 0)) {
cout << "\nInteger overflow!" << endl;
cout << "diff: " << diff << ", numerator: " << numerator << " denominator: " << denominator << endl;
return;
}
if (diff == 0.0) {
cout << " Exact result: ";
cout << (isNegative ? -numerator : numerator) << "/" << denominator << endl;
} else if (diff <= FLT_MIN) {
cout << "Approximate result: ";
cout << (isNegative ? -numerator : numerator) << "/" << denominator << endl;
} else {
cout << "You've got bugs... :( " << endl;
cout << "diff: " << diff << ", num:" << numerator << ", den: " << denominator << endl;
}
}
int main(void) {
cout << "\nworking on: (31 / 65537) " << endl;
rationalize(4.7301524329767917359659429024826e-4);
cout << "\nworking on: (262139 / 2^31-1) " << endl;
rationalize(1.220679842504057959888157416083e-4);
cout << "\nworking on: (-262147 / 2^31-1) " << endl;
rationalize(-1.2207170954070599262635502620896e-4);
cout << "\nworking on: (1048573 / 2147483647)" << endl;
rationalize(4.882798532435111018100339462096e-4);
cout << "\nworking on: (-1048583 / 2147483647)" << endl;
rationalize(-4.8828450985638634760695805196043e-4);
getchar();
return EXIT_SUCCESS;
}
Вы можете сделать это с помощью GMP:
mpq_t op;
mpq_set_d(op, number);
mpq_canonicalize(op);
long numer = mpz_get_si(mpq_numref(op));
long denom = mpz_get_si(mpq_denref(op));
Ref: https://gmplib.org/manual/Rational-Number-Functions.html
Других решений пока нет …