Flow algorithm for optimizing floats

Question

Given a floating point number, I want to get a String representation of a rational number approximating a decimal (accurate to a given tolerance ε). 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 are not familiar with it, ApintMath.pow will work even with arbitrarily long numbers, which is good because I am trying to convert decimal numbers with thousands of decimal places. The performance of my algorithm is terrible.

I attribute this to two things, but maybe more:

• My approach to getting a share is pretty naive. I am sure there is a better way.
• A fraction is not simplified, so any subsequent calculations using this fraction are likely to be time-consuming.

How do you do this? Are there other areas that I have not mentioned that slow me down?

Answer 1

Here the implementation of the Stern-Brocot tree is shown here , but you will need to look at the profile that is better.

Application: I 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 appropriate exceptions for undefined values.