加速翻倍理性数字转换
问题描述:
我写了一个相对简单的代码,将双精度转换为有理数。代码起作用,并且保证为给定的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;
}
答
可以使用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));
我想你希望在这里使用GCD。 –
你不能在'double'中存储最合理的值,因此你的解决方案将无法工作。所有双打实际上都是有理数值形式'有效数/ 2 ^( - exp)' –
a)我想将双数转换为有理数而不是其他方式,b)根据我的代码,范围限制为:[1/(2^31 - 1).. 2^31 - 1] c)IEEE-754双打仅表示有限数量的双打d)它不一定必须是*精确*:if(diff JSz