c++ - 加快双倍到有理数的转换

Question

我写了一个相对简单的代码来将 double 转换为有理数。该代码有效，并且保证找到给定 double 的最小有理数；但是，它比一月份的糖蜜慢。我花了一天时间尝试了各种方法来改进它，但无济于事。关于如何加快速度的任何想法？实际算法在 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; 
}

Answer 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));

引用:https://gmplib.org/manual/Rational-Number-Functions.html