java - 使浮点数合理化的高性能算法

Question

给定一个浮点数，我希望得到一个String近似小数的有理数的表示（在给定的容差 ε 内很好）。我目前的做法如下：

String rationalize(double d)
{
    String s = Double.toString(d);
    s = s.substring(s.indexOf('.')+1, s.length());
    return s + " / " + ApintMath.pow(new Apint(10), s.length()).toString();
}

如果您不熟悉它，ApintMath.pow甚至可以使用任意长的数字，这很好，因为我正在尝试转换具有数千个小数位的小数。我的算法的性能很糟糕。

我将此归因于两件事，但可能还有更多：

1. 我获得分数的方法非常幼稚。我确信有更好的方法。
2. 该分数是未简化的，因此使用该分数的任何后续计算都可能会浪费大量时间。

你会怎么做？还有其他我没有谈到的领域让我慢下来吗？

Answer 1

这里展示了一个 Stern–Brocot 树的实现，但您必须进行概要分析才能看到哪个更好。

附录：我org.jscience.mathematics.number.Rational在线性系统中使用效果很好；org.apache.commons.math.fraction.BigFraction提供了几个double可能有用的构造函数。所有未定义的值都会引发适当的异常。