加速翻倍理性數字轉換

Question

我寫了一個相對簡單的代碼，將雙精度轉換爲有理數。代碼起作用，並且保證爲給定的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