6

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?

Chris Dennett
  • 22,412
  • 8
  • 58
  • 84
Andy Shulman
  • 1,895
  • 3
  • 23
  • 32

1 Answers1

3

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.

trashgod
  • 203,806
  • 29
  • 246
  • 1,045
  • Unfortunately the library I'm using for rational numbers throws an exception on trying to construct 1/0. – Andy Shulman Apr 02 '12 at 17:53
  • I'm not familiar with that library, but it sounds like the right thing to do. I've cited a few alternatives above. – trashgod Apr 02 '12 at 21:05
  • Worked around the problem -- used a Stern-Brocot tree but narrowed the scope because I knew I wouldn't have rationals above or below certain values. Thanks for the suggestion. – Andy Shulman Apr 02 '12 at 22:00
  • Good idea. Looking closer, I see that this [`Rational`](http://introcs.cs.princeton.edu/java/92symbolic/Rational.java.html) ignores a zero denominator, using `Rational(1/0)` as positive infinity. – trashgod Apr 03 '12 at 06:59
  • 1
    Note for anyone else reading this: a Stern-Brocot tree is not faster than the algorithm I posted above in that they come up with the answer more slowly. However, they generate fractions that are smaller and much faster to perform computations with, at least for my application. – Andy Shulman Apr 03 '12 at 16:09