使浮动合理化的高性能算法

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\xe2\x80\x93Brocot 树实现，但您必须进行分析才能了解哪个更好。

\n\n

附录：我org.jscience.mathematics.number.Rational在线性系统中使用得到了很好的结果；org.apache.commons.math.fraction.BigFraction提供了几个double可能有用的构造函数。所有这些都会针对未定义的值抛出合适的异常。

\n