作为有理数的浮点数的精确值-解网

问：

我正在寻找一种方法将浮点数的精确值转换为两个整数的有理商，即，其中不大于指定的最大分母。如果无法满足条件，则结果将回退到仍满足条件的最佳近似值。a / bbb_maxb <= b_max

坚持。这里有很多关于截断实数的最佳有理近似的问题/答案，它被表示为浮点数。但是，我对浮点数的确切值感兴趣，浮点数本身就是一个具有不同表示的有理数。更具体地说，浮点数的数学集合是有理数的子集。在 IEEE 754 二进制浮点标准的情况下，它是二元有理数的子集。无论如何，任何浮点数都可以转换为两个有限精度整数的有理商。a / b

因此，例如，假设 IEEE 754 单精度二进制浮点格式，则的有理等价物不是，而是。这是的确切值，它是 IEEE 754 单精度二进制浮点数数学集中的一个数字。float f = 1.0f / 3.0f1 / 311184811 / 33554432f

根据我的经验，遍历（通过二进制搜索）Stern-Brocot 树在这里没有用，因为它更适合于近似浮点数的值，当它被解释为截断实数而不是精确有理数时。

可能，持续的分数是要走的路。

这里的另一个问题是整数溢出。想一想，我们想把有理数表示为 2 的商，其中最大分母。我们不能依赖像这样的停止标准。因此，算法绝不能溢出，或者必须检测溢出。int32_tb_max = INT32_MAXb > b_max

到目前为止，我发现的是 Rosetta Code 中的一种算法，它基于连续分数，但其来源提到它“仍然不完全”。一些基本测试给出了很好的结果，但我无法确认它的整体正确性，我认为它很容易溢出。

// https://rosettacode.org/wiki/Convert_decimal_number_to_rational#C

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

/* f : number to convert.
 * num, denom: returned parts of the rational.
 * md: max denominator value.  Note that machine floating point number
 *     has a finite resolution (10e-16 ish for 64 bit double), so specifying
 *     a "best match with minimal error" is often wrong, because one can
 *     always just retrieve the significand and return that divided by 
 *     2**52, which is in a sense accurate, but generally not very useful:
 *     1.0/7.0 would be "2573485501354569/18014398509481984", for example.
 */
void rat_approx(double f, int64_t md, int64_t *num, int64_t *denom)
{
    /*  a: continued fraction coefficients. */
    int64_t a, h[3] = { 0, 1, 0 }, k[3] = { 1, 0, 0 };
    int64_t x, d, n = 1;
    int i, neg = 0;

    if (md <= 1) { *denom = 1; *num = (int64_t) f; return; }

    if (f < 0) { neg = 1; f = -f; }

    while (f != floor(f)) { n <<= 1; f *= 2; }
    d = f;

    /* continued fraction and check denominator each step */
    for (i = 0; i < 64; i++) {
        a = n ? d / n : 0;
        if (i && !a) break;

        x = d; d = n; n = x % n;

        x = a;
        if (k[1] * a + k[0] >= md) {
            x = (md - k[0]) / k[1];
            if (x * 2 >= a || k[1] >= md)
                i = 65;
            else
                break;
        }

        h[2] = x * h[1] + h[0]; h[0] = h[1]; h[1] = h[2];
        k[2] = x * k[1] + k[0]; k[0] = k[1]; k[1] = k[2];
    }
    *denom = k[1];
    *num = neg ? -h[1] : h[1];
}

C++ 浮点值方法有理数续分数

您可能对 Python 的 Fraction.limit_denominator 感兴趣，它正是这样做的。当然，这并不能帮助解决 C 语言中的溢出问题，但该算法可能很有用。具体来说，在 Python 中，for a （Python）给出你想要的东西。floatxFraction(x).limit_denominator(b_max)

1赞 Eric Postpischil 7/3/2018

chux 给出了一个可能适合 IEEE-754 二进制格式的答案（我还没有检查过）。为了完整起见，我将指出 C 提供了，它定义了用于浮点格式的基数。乘法或除以应该是精确的（并注意函数），因此，给定一些不是整数的浮点值，可以通过乘以找到所需的分子，直到结果为整数，分母是乘法次数的幂。FLT_RADIXFLT_RADIXscalbnxFLT_RADIXFLT_RADIX

答：

8赞 chux - Reinstate Monica 7/3/2018 #1

所有有限都是有理数，正如 OP 所说的那样。double

用于将数字分解为分数和指数。由于范围要求，最终结果仍需要用于表示整数值。有些数字太小，（小于）和无穷大，不是数字是问题。frexp()doublex1.0/(2.0,DBL_MAX_EXP)

这些函数将浮点数分解为归一化分数和 2 的整数幂。...间隔 [1/2， 1）或零 ...
C11 §7.12.6.4 2/3frexp

#include <math.h>
#include <float.h>

_Static_assert(FLT_RADIX == 2, "TBD code for non-binary FP");

// Return error flag
int split(double x, double *numerator, double *denominator) {
  if (!isfinite(x)) {
    *numerator = *denominator = 0.0;
    if (x > 0.0) *numerator = 1.0;
    if (x < 0.0) *numerator = -1.0;
    return 1;
  }
  int bdigits = DBL_MANT_DIG;
  int expo;
  *denominator = 1.0;
  *numerator = frexp(x, &expo) * pow(2.0, bdigits);
  expo -= bdigits;
  if (expo > 0) {
    *numerator *= pow(2.0, expo);
  }
  else if (expo < 0) {
    expo = -expo;
    if (expo >= DBL_MAX_EXP-1) {
      *numerator /= pow(2.0, expo - (DBL_MAX_EXP-1));
      *denominator *= pow(2.0, DBL_MAX_EXP-1);
      return fabs(*numerator) < 1.0;
    } else {
      *denominator *= pow(2.0, expo);
    }
  }

  while (*numerator && fmod(*numerator,2) == 0 && fmod(*denominator,2) == 0) {
    *numerator /= 2.0;
    *denominator /= 2.0;
  }
  return 0;
}

void split_test(double x) {
  double numerator, denominator;
  int err = split(x, &numerator, &denominator);
  printf("e:%d x:%24.17g n:%24.17g d:%24.17g q:%24.17g\n", 
      err, x, numerator, denominator, numerator/ denominator);
}

int main(void) {
  volatile float third = 1.0f/3.0f;
  split_test(third);
  split_test(0.0);
  split_test(0.5);
  split_test(1.0);
  split_test(2.0);
  split_test(1.0/7);
  split_test(DBL_TRUE_MIN);
  split_test(DBL_MIN);
  split_test(DBL_MAX);
  return 0;
}

输出

e:0 x:      0.3333333432674408 n:                11184811 d:                33554432 q:      0.3333333432674408
e:0 x:                       0 n:                       0 d:        9007199254740992 q:                       0
e:0 x:                       1 n:                       1 d:                       1 q:                       1
e:0 x:                     0.5 n:                       1 d:                       2 q:                     0.5
e:0 x:                       1 n:                       1 d:                       1 q:                       1
e:0 x:                       2 n:                       2 d:                       1 q:                       2
e:0 x:     0.14285714285714285 n:        2573485501354569 d:       18014398509481984 q:     0.14285714285714285
e:1 x: 4.9406564584124654e-324 n:  4.4408920985006262e-16 d: 8.9884656743115795e+307 q: 4.9406564584124654e-324
e:0 x: 2.2250738585072014e-308 n:                       2 d: 8.9884656743115795e+307 q: 2.2250738585072014e-308
e:0 x: 1.7976931348623157e+308 n: 1.7976931348623157e+308 d:                       1 q: 1.7976931348623157e+308

将考虑留待以后再考虑。b_max

更方便的代码可以替换为 @gammatester 或 @Bob__pow(2.0, expo)ldexp(1, expo)exp2(expo)

while (*numerator && fmod(*numerator,2) == 0 && fmod(*denominator,2) == 0)还可以使用一些性能改进。但首先，让我们根据需要获得功能。

作为有理数的浮点数的精确值

Exact value of a floating-point number as a rational

评论

评论