如何将ieee754双打转换为两个整数的分数？

如何获得long long（64位）从double（64位）值d这样(double)a/b或多或少等于d值a和b？这是可能的（不失精度）？如何将ieee754双打转换为两个整数的分数？

我沿着这个线路尝试，但它并没有取得任何进展，所以我想，也许我有错误的观念：

union ieee754_double u; 
u.d = d; 

long long a = (long long)u.ieee.mantissa0 << 32 | u.ieee.mantissa1; 
long long b = (long long)1 << (u.ieee.exponent + IEEE754_DOUBLE_BIAS);

来源

2013-04-30 antak

[续分]（http://en.wikipedia.org/wiki/Continued_fraction） – 2013-04-30 10:22:05

您需要在尾数中缺少隐式前导1。 – 2013-04-30 10:28:39

找到两个整数“p”和“q”是可能的（而且确实很容易），使得它们之间的比率恰好等于双倍（除了NaN和无穷大外）。但通常其中一个会比64位长。 – harold 2013-04-30 10:37:03

根据意见，一些其他的答案和纯试错的，我想出了这个（这似乎或多或少工作）：

union ieee754_double u; 
u.d = d; 

long long a = (long long)(!u.ieee.exponent && u.ieee.exponent != 0x7ff) << 52 | 
     (long long)u.ieee.mantissa0 << 32 | u.ieee.mantissa1; 
int exp = IEEE754_DOUBLE_BIAS - u.ieee.exponent + 52; 

long long b; 
if (u.ieee.exponent != 0x7ff) { 
    if (exp > 62) { 
     a >>= exp - 62; 
     exp = 62; 
    } 
    if (exp < 0) { 
     a <<= 0 - exp; 
     exp = 0; 
    } 
    b = 1LL << exp; 
} else { 
    b = 0; 
} 

a = u.ieee.negative ? -a : a;

我还在试图找出哪里的边缘，但因为我移出位，我认为它的无损高达+/-2**62和向下2**-10

做一些来回测试与atof(argv[1]) - >printf()），我似乎能重现值高达+/-2**53并降至2**-18（只要我轮了）。我猜2**53是double的限制。

来源

2013-05-02 06:18:28 antak

每一个浮点数，除了无穷大和NaN可以精确地表示为两个整数的比率。一些双精度浮点数需要整数大于64位 - 例如，1e-300将转换为6032057205060441/(2 ** 1049)。但是，大致在范围(2**-40, 2**63)内的浮点数可以无损地转换为两个64位整数的一部分。

这样的转换函数的一个例子是Python的浮点对象的as_integer_ratio()方法。在Python/C-ESE翻译，代码如下所示：

#include <math.h> 
#include <stdlib.h> 

void double_as_ratio(double flt, long long *numerator, long long *denominator) 
{ 
    double float_part; 
    int exponent; 
    long long long_exponent; 
    int i; 

    float_part = frexp(flt, &exponent); /* flt == float_part * 2**exponent exactly */ 
    for (i=0; i<300 && float_part != floor(float_part) ; i++) { 
     float_part *= 2.0; 
     exponent--; 
    } 
    /* flt == float_part * 2**exponent exactly and float_part is integral. */ 

    *numerator = (long long) float_part;   /* can overflow */ 
    long_exponent = 1LL << labs((long) exponent); /* can overflow */ 
    if (exponent > 0) { 
     *numerator *= long_exponent; 
     *denominator = 1; 
    } 
    else 
     *denominator = long_exponent; 
}

这个代码不依赖于位的精确布局，只有依赖于C89所需的frexp和floor功能。应用于浮点值0.1，它会生成正确的值3602879701896397和36028797018963968。

来源

2013-04-30 10:54:12 user4815162342

这个答案完全正确，让我想起了气球笑话:-) – Ben 2013-04-30 11:33:32

@本：不，它不完全正确。 “我”需要高达1076左右才能正确处理低于正常值的事件。还有许多其他问题，如溢出所述。我还要指出，除了低于正常情况外，“双”完全能够代表相关的分子和分母。你根本不需要任意精度的验证。 – tmyklebu 2013-04-30 11:41:44

@tmyklebu它真的需要处理次正常吗？ Python似乎没有它。溢出问题可以通过使用bigint来纠正（使用双打似乎是圆形的），但OP明确要求“long long”。 – user4815162342 2013-04-30 12:03:22

你究竟在做什么？如果你将double转换为理性的，你几乎肯定需要一个近似的答案。

你想要它有多准确？如果答案正好是244653797/159601597，你想要那个答案吗？我非常怀疑它。你想更喜欢小数？或者分数较小的分数？或者是什么？

0.4286应该是4286/10000 = 2143/500还是1/7？

0.428应该是107/250还是1/7？

不知道你实际试图解决什么问题，很难解决它。

来源

2013-04-30 11:01:20 Ben

@HighPerformanceMark，更正:-) – Ben 2013-04-30 11:28:39

请注意，浮点数的分母总是2的幂，所以'244653797/159601597'不能是确切的答案。 – user4815162342 2013-04-30 12:30:03

@ user4815162342，好点:-)，但我确信他希望'1.0f/7.0f'解析回1/7。 – Ben 2013-04-30 13:22:44

Dan Steffy写道code for rational reconstruction这非常简单且具有启发性的阅读。如果你想a和b使a/b轮正确double和b是相当小的，叫reconstruct_bits至53

时所设置的参数bits我相信代码工作由连分数近似。值得注意的是，对于给定的分母界限或相对误差界限，这不一定会产生最佳有理逼近。它产生了所有可以将所有可能的分母边界相关的数量最小化的理性重构（目前无法回避）。

来源

2013-04-30 11:28:50 tmyklebu

如何将ieee754双打转换为两个整数的分数？

回答

相关问题