Performant algorithm to rationalize floats

Question

Given a floating point number, I'm looking to get a String representation of a rational number approximating the decimal (to within a given tolerance ε is fine). My current approach is as follows:

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();
}

If you're unfamiliar with it, ApintMath.pow will work even with arbitrarily long numbers, which is good because I'm attempting to convert decimals with thousands of decimal places. The performance of my algorithm is terrible.

I attribute this to two things, but there could be more:

1. My approach to getting a fraction is pretty naive. I'm sure there's a better way.
2. The fraction is unsimplified, so any subsequent calculations using this fraction are likely going to waste a lot of time.

How would you do this? Are there other areas I haven't talked about that are slowing me down?

Answer 1

There's a Stern–Brocot tree implementation shown here, but you'll have to profile to see which is better.

Addendum: I've had good results using org.jscience.mathematics.number.Rational in linear systems; org.apache.commons.math.fraction.BigFraction offers several constructors for double that may be useful. All throw suitable exceptions for undefined values.