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:
- My approach to getting a fraction is pretty naive. I'm sure there's a better way.
- 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?
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 fordouble
that may be useful. All throw suitable exceptions for undefined values.