0

我有将双精度（比如N）转换为 p/q 形式（有理形式）的问题，为此我有以下策略：

  1. 将 N 乘以一个大数，例如 $k = 10^{10}$
  2. 然后p = y*k和q = k
  3. 拿来gcd(p,q)找找p = p/gcd(p,q)_q = p/gcd(p,q)

时N = 8.2，如果我们用纸笔解决，答案是正确的，但如(double)中8.2表示的那样，它会导致其有理形式转换出现问题。8.19999999N

我尝试过其他方式：（我使用了一个大号 10^k 而不是 100）

if(abs(y*100 - round(y*100)) < 0.000001) y = round(y*100)/100

但是这种方法也不能一直给出正确的表示。

有什么办法可以进行从 double 到 p/q 的等效转换？

4

2 回答 2

1

浮点运算非常困难。正如评论中提到的，部分困难在于您需要用二进制表示您的数字。

例如，数字 0.125 可以用二进制精确表示：

0.125 = 2^-3 = 0b0.001

但是数字 0.12 不能。

至 11 位有效数字：

0.12 = 0b0.00011110101

如果将其转换回小数，则错误变得很明显：

0b0.00011110101 = 0.11962890625

所以如果你写：

double a = 0.2;

机器实际上所做的是找到它可以在双精度数据类型中保存的最接近的 0.2 二进制表示。这是一个近似值，因为正如我们在上面看到的，0.2 不能用二进制精确表示。

一种可能的方法是定义一个“epsilon”，它确定您的数字与最近的可表示二进制浮点数的接近程度。

这是一篇关于浮点的好文章：

https://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/

于 2018-02-11T12:07:47.910 回答
1

将双精度（例如N）转换为 p/q 形式时存在问题
...当 N = 8.2

一个典型的double不能完全编码8.2。相反，最接近的可表示double是关于

8.19999999999999928945726423989981412887573...
8.20000000000000106581410364015027880668640...  // next closest

当代码执行

double N = 8.2;

它将8.19999999999999928945726423989981412887573...被转换为理性形式。

将 a 转换double为 p/q 形式：

将 N 乘以一个大数，例如 $k = 10^{10}$

这可能会溢出double. 第一步应该是确定是否double很大，它是什么情况，它是一个整数。

不要乘以 10 的幂，因为double肯定使用二进制编码。乘以 10、100 等可能会引入舍入误差。

绝大多数的C 实现double使用二进制编码，因此FLT_RADIX == 2.

然后每个有限double x都有一个有效数字，它是某个整数的分数超过 2 的某个幂：数字的二进制分数DBL_MANT_DIG@Richard Critten。这通常是 53 个二进制数字。

确定 的指数double。如果足够大 或x == 0.0，double是一个整数。

否则，将分子和分母按比例缩放DBL_MANT_DIG。当分子是偶数时，将分子和分母都减半。由于denominator是 2 的幂，因此出于简化考虑，不需要其他素数。

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

void form_ratio(double x) {
  double numerator = x;
  double denominator = 1.0;
  if (isfinite(numerator) && x != 0.0) {
    int expo;
    frexp(numerator, &expo);
    if (expo < DBL_MANT_DIG) {
      expo = DBL_MANT_DIG - expo;
      numerator = ldexp(numerator, expo);
      denominator = ldexp(1.0, expo);
      while (fmod(numerator, 2.0) == 0.0 && denominator > 1.0) {
        numerator /= 2.0;
        denominator /= 2.0;
      }
    }
  }
  int pre = DBL_DECIMAL_DIG;
  printf("%.*g --> %.*g/%.*g\n", pre, x, pre, numerator, pre, denominator);
}

int main(void) {
  form_ratio(123456789012.0);
  form_ratio(42.0);
  form_ratio(1.0 / 7);
  form_ratio(867.5309);
}

输出

123456789012 --> 123456789012/1
42 --> 42/1
0.14285714285714285 --> 2573485501354569/18014398509481984
867.53089999999997 --> 3815441248019913/4398046511104
于 2018-02-11T14:46:47.837 回答