ускорение двойного преобразования в рациональное число

Я написал относительно простой код для преобразования парных чисел в рациональные числа. Код работает, и он гарантированно найдет наименьшее рациональное число для данного двойного числа; однако, это медленнее, чем патока в январе. Я провел день, пробуя различные методы, чтобы улучшить его безрезультатно. Есть идеи, как это ускорить? Фактический алгоритм находится в цикле 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;
}

1

Решение

Вы можете сделать это с помощью 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

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]