title: Algorithm for finding the ratio of two floating-point numbers?
body: <p>I need to find the ratio of one floating-point number to another, and the ratio needs to be two integers. For example:</p>
  
  <ul>
  <li>input: <code>1.5, 3.25</code></li>
  <li>output: <code>"6:13"</code></li>
  </ul>
  
  <p>Does anyone know of one? Searching the internet, I found no such algorithm, nor an algorithm for the least common multiple or denominator of two floating-point numbers (just integers).</p>
  
  <h2>Java implementation:</h2>
  
  <hr>
  
  <p>This is the final implementation that I will use:</p>
  
  <pre class="lang-java prettyprint-override"><code>public class RatioTest
  {
    public static String getRatio(double d1, double d2)//1.5, 3.25
    {
      while(Math.max(d1,d2) &lt; Long.MAX_VALUE &amp;&amp; d1 != (long)d1 &amp;&amp; d2 != (long)d2)
      {
        d1 *= 10;//15 -&gt; 150
        d2 *= 10;//32.5 -&gt; 325
      }
      //d1 == 150.0
      //d2 == 325.0
      try
      {
        double gcd = getGCD(d1,d2);//gcd == 25
        return ((long)(d1 / gcd)) + ":" + ((long)(d2 / gcd));//"6:13"
      }
      catch (StackOverflowError er)//in case getGDC (a recursively looping method) repeats too many times
      {
        throw new ArithmeticException("Irrational ratio: " + d1 + " to " + d2);
      }
    }
  
    public static double getGCD(double i1, double i2)//(150,325) -&gt; (150,175) -&gt; (150,25) -&gt; (125,25) -&gt; (100,25) -&gt; (75,25) -&gt; (50,25) -&gt; (25,25)
    {
      if (i1 == i2)
        return i1;//25
      if (i1 &gt; i2)
        return getGCD(i1 - i2, i2);//(125,25) -&gt; (100,25) -&gt; (75,25) -&gt; (50,25) -&gt; (25,25)
      return getGCD(i1, i2 - i1);//(150,175) -&gt; (150,25)
    }
  }
  </code></pre>
  
  <ul>
  <li><code>-&gt;</code> indicates the next stage in the loop or method call</li>
  </ul>
  
  <h2>Mystical's implementation as Java:</h2>
  
  <hr>
  
  <p>Though I did not end up using this, it more than deserves to be recognized, so I translated it to Java, so I could understand it:</p>
  
  <pre class="lang-java prettyprint-override"><code>import java.util.Stack;
  
  public class RatioTest
  {
      class Fraction{
          long num;
          long den;
          double val;
      };
  
      Fraction build_fraction(Stack&lt;long&gt; cf){
          long term = cf.size();
          long num = cf[term - 1];
          long den = 1;
          while (term-- &gt; 0){
              long tmp = cf[term];
  
              long new_num = tmp * num + den;
              long new_den = num;
  
              num = new_num;
              den = new_den;
          }
  
          Fraction f;
          f.num = num;
          f.den = den;
          f.val = (double)num / (double)den;
  
          return f;
      }
  
      void get_fraction(double x){
          System.out.println("x = " + x);
  
          //  Generate Continued Fraction
          System.out.print("Continued Fraction: ");
          double t = Math.abs(x);
          double old_error = x;
          Stack&lt;long&gt; cf;
          Fraction f;
          do{
              //  Get next term.
              long tmp = (long)t;
              cf.push(tmp);
  
              //  Build the current convergent
              f = build_fraction(cf);
  
              //  Check error
              double new_error = Math.abs(f.val - x);
              if (tmp != 0 &amp;&amp; new_error &gt;= old_error){
                  //  New error is bigger than old error.
                  //  This means that the precision limit has been reached.
                  //  Pop this (useless) term and break out.
                  cf.pop();
                  f = build_fraction(cf);
                  break;
              }
              old_error = new_error;
              System.out.print(tmp + ", ");
  
              //  Error is zero. Break out.
              if (new_error == 0)
                  break;
  
              t -= tmp;
              t = 1/t;
          }while (cf.size() &lt; 39); //  At most 39 terms are needed for double-precision.
          System.out.println();System.out.println();
  
          //  Print Results
          System.out.println("The fraction is:   " + f.num + " / " + f.den);
          System.out.println("Target x = " + x);
          System.out.println("Fraction = " + f.val);
          System.out.println("Relative error is: " + (Math.abs(f.val - x) / x));System.out.println();
          System.out.println();
      }
      public static void main(String[] args){
          get_fraction(15.38 / 12.3);
          get_fraction(0.3333333333333333333);    //  1 / 3
          get_fraction(0.4184397163120567376);    //  59 / 141
          get_fraction(0.8323518818409020299);    //  1513686 / 1818565
          get_fraction(3.1415926535897932385);    //  pi
      }
  }
  </code></pre>
  
  <h2>One MORE thing:</h2>
  
  <hr>
  
  <p>The above mentioned implemented way of doing this works <strong>IN THEORY</strong>, however, due to floating-point rounding errors, this results in alot of unexpected exceptions, errors, and outputs. Below is a practical, robust, but a bit dirty implementation of a ratio-finding algorithm (Javadoc'd for your convenience):</p>
  
  <pre class="lang-java prettyprint-override"><code>public class RatioTest
  {
    /** Represents the radix point */
    public static final char RAD_POI = '.';
  
    /**
     * Finds the ratio of the two inputs and returns that as a &lt;tt&gt;String&lt;/tt&gt;
     * &lt;h4&gt;Examples:&lt;/h4&gt;
     * &lt;ul&gt;
     * &lt;li&gt;&lt;tt&gt;getRatio(0.5, 12)&lt;/tt&gt;&lt;ul&gt;
       *   &lt;li&gt;returns "&lt;tt&gt;24:1&lt;/tt&gt;"&lt;/li&gt;&lt;/ul&gt;&lt;/li&gt;
     * &lt;li&gt;&lt;tt&gt;getRatio(3, 82.0625)&lt;/tt&gt;&lt;ul&gt;
     *   &lt;li&gt;returns "&lt;tt&gt;1313:48&lt;/tt&gt;"&lt;/li&gt;&lt;/ul&gt;&lt;/li&gt;
     * &lt;/ul&gt;
     * @param d1 the first number of the ratio
     * @param d2 the second number of the ratio
     * @return the resulting ratio, in the format "&lt;tt&gt;X:Y&lt;/tt&gt;"
     */
    public static strictfp String getRatio(double d1, double d2)
    {
      while(Math.max(d1,d2) &lt; Long.MAX_VALUE &amp;&amp; (!Numbers.isCloseTo(d1,(long)d1) || !Numbers.isCloseTo(d2,(long)d2)))
      {
        d1 *= 10;
        d2 *= 10;
      }
      long l1=(long)d1,l2=(long)d2;
      try
      {
        l1 = (long)teaseUp(d1); l2 = (long)teaseUp(d2);
        double gcd = getGCDRec(l1,l2);
        return ((long)(d1 / gcd)) + ":" + ((long)(d2 / gcd));
      }
      catch(StackOverflowError er)
      {
        try
        {
          double gcd = getGCDItr(l1,l2);
          return ((long)(d1 / gcd)) + ":" + ((long)(d2 / gcd));
        }
        catch (Throwable t)
        {
          return "Irrational ratio: " + l1 + " to " + l2;
        }
      }
    }
  
  
    /**
     * &lt;b&gt;Recursively&lt;/b&gt; finds the Greatest Common Denominator (GCD)
     * @param i1 the first number to be compared to find the GCD
     * @param i2 the second number to be compared to find the GCD
     * @return the greatest common denominator of these two numbers
     * @throws StackOverflowError if the method recurses to much
     */
    public static long getGCDRec(long i1, long i2)
    {
      if (i1 == i2)
        return i1;
      if (i1 &gt; i2)
        return getGCDRec(i1 - i2, i2);
      return getGCDRec(i1, i2 - i1);
    }
  
    /**
     * &lt;b&gt;Iteratively&lt;/b&gt; finds the Greatest Common Denominator (GCD)
     * @param i1 the first number to be compared to find the GCD
     * @param i2 the second number to be compared to find the GCD
     * @return the greatest common denominator of these two numbers
     */
    public static long getGCDItr(long i1, long i2)
    {
      for (short i=0; i &lt; Short.MAX_VALUE &amp;&amp;  i1 != i2; i++)
      {
        while (i1 &gt; i2)
          i1 = i1 - i2;
        while (i2 &gt; i1)
          i2 = i2 - i1;
      }
        return i1;
    }
  
    /**
     * Calculates and returns whether &lt;tt&gt;d1&lt;/tt&gt; is close to &lt;tt&gt;d2&lt;/tt&gt;
     * &lt;h4&gt;Examples:&lt;/h4&gt;
     * &lt;ul&gt;
     * &lt;li&gt;&lt;tt&gt;d1 == 5&lt;/tt&gt;, &lt;tt&gt;d2 == 5&lt;/tt&gt;
     *   &lt;ul&gt;&lt;li&gt;returns &lt;tt&gt;true&lt;/tt&gt;&lt;/li&gt;&lt;/ul&gt;&lt;/li&gt;
     * &lt;li&gt;&lt;tt&gt;d1 == 5.0001&lt;/tt&gt;, &lt;tt&gt;d2 == 5&lt;/tt&gt;
     *   &lt;ul&gt;&lt;li&gt;returns &lt;tt&gt;true&lt;/tt&gt;&lt;/li&gt;&lt;/ul&gt;&lt;/li&gt;
     * &lt;li&gt;&lt;tt&gt;d1 == 5&lt;/tt&gt;, &lt;tt&gt;d2 == 5.0001&lt;/tt&gt;
     *   &lt;ul&gt;&lt;li&gt;returns &lt;tt&gt;true&lt;/tt&gt;&lt;/li&gt;&lt;/ul&gt;&lt;/li&gt;
     * &lt;li&gt;&lt;tt&gt;d1 == 5.24999&lt;/tt&gt;, &lt;tt&gt;d2 == 5.25&lt;/tt&gt;
     *   &lt;ul&gt;&lt;li&gt;returns &lt;tt&gt;true&lt;/tt&gt;&lt;/li&gt;&lt;/ul&gt;&lt;/li&gt;
     * &lt;li&gt;&lt;tt&gt;d1 == 5.25&lt;/tt&gt;, &lt;tt&gt;d2 == 5.24999&lt;/tt&gt;
     *   &lt;ul&gt;&lt;li&gt;returns &lt;tt&gt;true&lt;/tt&gt;&lt;/li&gt;&lt;/ul&gt;&lt;/li&gt;
     * &lt;li&gt;&lt;tt&gt;d1 == 5&lt;/tt&gt;, &lt;tt&gt;d2 == 5.1&lt;/tt&gt;
     *   &lt;ul&gt;&lt;li&gt;returns &lt;tt&gt;false&lt;/tt&gt;&lt;/li&gt;&lt;/ul&gt;&lt;/li&gt;
     * &lt;/ul&gt;
     * @param d1 the first number to compare for closeness
     * @param d2 the second number to compare for closeness
     * @return &lt;tt&gt;true&lt;/tt&gt; if the two numbers are close, as judged by this method
     */
    public static boolean isCloseTo(double d1, double d2)
    {
      if (d1 == d2)
        return true;
      double t;
      String ds = Double.toString(d1);
      if ((t = teaseUp(d1-1)) == d2 || (t = teaseUp(d2-1)) == d1)
        return true;
      return false;
    }
  
    /**
     * continually increases the value of the last digit in &lt;tt&gt;d1&lt;/tt&gt; until the length of the double changes
     * @param d1
     * @return
     */
    public static double teaseUp(double d1)
    {
      String s = Double.toString(d1), o = s;
      byte b;
      for (byte c=0; Double.toString(extractDouble(s)).length() &gt;= o.length() &amp;&amp; c &lt; 100; c++)
        s = s.substring(0, s.length() - 1) + ((b = Byte.parseByte(Character.toString(s.charAt(s.length() - 1)))) == 9 ? 0 : b+1);
      return extractDouble(s);
    }
  
    /**
     * Works like Double.parseDouble, but ignores any extraneous characters. The first radix point (&lt;tt&gt;.&lt;/tt&gt;) is the only one treated as such.&lt;br/&gt;
     * &lt;h4&gt;Examples:&lt;/h4&gt;
     * &lt;li&gt;&lt;tt&gt;extractDouble("123456.789")&lt;/tt&gt; returns the double value of &lt;tt&gt;123456.789&lt;/tt&gt;&lt;/li&gt;
     * &lt;li&gt;&lt;tt&gt;extractDouble("1qw2e3rty4uiop[5a'6.p7u8&amp;9")&lt;/tt&gt; returns the double value of &lt;tt&gt;123456.789&lt;/tt&gt;&lt;/li&gt;
     * &lt;li&gt;&lt;tt&gt;extractDouble("123,456.7.8.9")&lt;/tt&gt; returns the double value of &lt;tt&gt;123456.789&lt;/tt&gt;&lt;/li&gt;
     * &lt;li&gt;&lt;tt&gt;extractDouble("I have $9,862.39 in the bank.")&lt;/tt&gt; returns the double value of &lt;tt&gt;9862.39&lt;/tt&gt;&lt;/li&gt;
     * @param str The &lt;tt&gt;String&lt;/tt&gt; from which to extract a &lt;tt&gt;double&lt;/tt&gt;.
     * @return the &lt;tt&gt;double&lt;/tt&gt; that has been found within the string, if any.
     * @throws NumberFormatException if &lt;tt&gt;str&lt;/tt&gt; does not contain a digit between 0 and 9, inclusive.
     */
    public static double extractDouble(String str) throws NumberFormatException
    {
      try
      {
        return Double.parseDouble(str);
      }
      finally
      {
        boolean r = true;
        String d = "";
        for (int i=0; i &lt; str.length(); i++)
          if (Character.isDigit(str.charAt(i)) || (str.charAt(i) == RAD_POI &amp;&amp; r))
          {
            if (str.charAt(i) == RAD_POI &amp;&amp; r)
              r = false;
            d += str.charAt(i);
          }
        try
        {
          return Double.parseDouble(d);
        }
        catch (NumberFormatException ex)
        {
          throw new NumberFormatException("The input string could not be parsed to a double: " + str);
        }
      }
    }
  }
  </code></pre>