加速翻倍理性数字转换

问题描述：

我写了一个相对简单的代码，将双精度转换为有理数。代码起作用，并且保证为给定的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; 
}

我想你希望在这里使用GCD。 –

你不能在'double'中存储最合理的值，因此你的解决方案将无法工作。所有双打实际上都是有理数值形式'有效数/ 2 ^（ - exp）' –

a）我想将双数转换为有理数而不是其他方式，b）根据我的代码，范围限制为：[1/（2^31 - 1）.. 2^31 - 1] c）IEEE-754双打仅表示有限数量的双打d）它不一定必须是*精确*：if（diff JSz

答

可以使用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

加速翻倍理性数字转换

相关推荐