2

可能重复：
如何将浮点数转换为由字节分子和分母表示的最接近的分数？

我想在 Java 中采用任意浮点数或双精度数并将其转换为有理数 - 即。a/b 形式的数字，其中 a 和 b 是长整数。我怎样才能以合理有效的方式做到这一点？

（顺便说一句——我已经有了简化分数的代码，所以 a/b 是否是最简单的形式并不重要）。

4

5 回答 5

5

首先看看IEEE-754 规则是如何构造双精度（或浮点数，但我在下面仅指双精度）：

然后使用 . 将 double 转换为位Double.doubleToLongBits。用这种方法计算分数1 + bit_0 * 2^(-1) + bit_1 * 2^(-2) ...。将结果乘以指数（2^(exponent)准确地说）和一个符号。

这是代码：

double number =  -0.15625;
// Code below doesn't work for 0 and NaN - just check before

long bits = Double.doubleToLongBits(number);

long sign = bits >>> 63;
long exponent = ((bits >>> 52) ^ (sign << 11)) - 1023;
long fraction = bits << 12; // bits are "reversed" but that's not a problem

long a = 1L;
long b = 1L;

for (int i = 63; i >= 12; i--) {
    a = a * 2 + ((fraction >>> i) & 1);
    b *= 2;
}

if (exponent > 0)
    a *= 1 << exponent;
else
    b *= 1 << -exponent;

if (sign == 1)
    a *= -1;

// Here you have to simplify the fraction

System.out.println(a + "/" + b);

但要小心 - 使用大指数时，您可能会遇到不适合您的变量的数字。实际上，您可以考虑将指数存储在分数上，并且仅在指数足够小时才将其相乘。如果不是，您必须向用户显示分数，您可以使用科学记数法（这需要求解方程2^n = x * 10^m，其中 m 是您的十进制指数，x 是您必须乘以分数的数字。但这是另一个问题的问题...）。

于 2012-11-04T20:56:48.740 回答
2

让long bits = Double.doubleToLongBits(double). 来自的Javadoc Double.longBitsToDouble：

...让 s、e 和 m 是可以从参数计算的三个值：

int s = ((bits >> 63) == 0) ? 1 : -1;
int e = (int)((bits >> 52) & 0x7ffL);
long m = (e == 0) ?
             (bits & 0xfffffffffffffL) << 1 :
             (bits & 0xfffffffffffffL) | 0x10000000000000L;

然后浮点结果等于数学表达式 s·m·2 e-1075的值。

这个结果肯定是一个有理数。

于 2012-11-04T23:45:47.280 回答
1

任何 FP 值对应的有理数是 (mantissa/2^-exponent)，其中尾数和指数在IEEE 754（Wiki 参考）中定义。然后，您可以按 LCD（或者我猜是 GCF）应用除法以获得规范的有理数。

于 2012-11-04T21:35:21.670 回答
1

对于给定的最大分母，连续分数标题下包含的各种概念会产生最佳可能的有理近似值。具体来说，您要问的是计算收敛序列。在某些时候，当您的分母根据您想要的任何标准足够大（或被有限整数实现长度强加给您）时，终止计算收敛项并使用最后一个。在链接的维基百科页面上对算法进行了相当详细的描述。

To address one concern you raised, the fractions generated in the convergent sequence are always in reduced form. They are also provably the best possible approximations for a given denominator. Precisely, a convergent term of the form m/n is closer to the target number than another other fraction with denominator < n. In other words, the convergent algorithm yields better approximations than trial and error.

于 2012-11-05T00:27:42.607 回答
0

如您所知，浮点数甚至不能精确存储诸如 0.1 之类的简单数字。如果您使用一种天真的方法来转换浮点数，那么您最终可能会得到巨大的分子和分母。

但是，有些算法可能会有所帮助：Dragon4 和 Grisu3算法旨在为浮点数创建最易读的输出。他们利用某些浮点位序列可以用几个小数表示的优势，并选择其中最短的一个。

对于第一个实现，我将使用 Dragon4 和/或 Grisu3 从浮点中创建最短的小数部分。例如，带有位的浮点数cd cc cc cc cc cc f4 3f将导致十进制小数1.3而不是1.29999999。然后我会以 a/b 的形式表示小数部分并简化它。在给定的示例中，这将是13/10，没有进一步简化。

请注意，转换为小数可能是不利的。例如，有理数 1/3 不能同时用十进制数和浮点数精确表示。因此，最好的解决方案是修改诸如 Dragon4 之类的算法以使用任意小数分母，而不仅仅是 10。唉，这几乎肯定需要大量的工作和一些 CS 背景。

于 2012-11-04T21:26:18.190 回答