Алгоритм определения отношения двух чисел с плавающей запятой?

Мне нужно найти отношение одного числа с плавающей запятой к другому, и это отношение должно быть двумя целыми числами. Например:

• ввод: 1.5, 3.25
• вывод: «6:13»

Кто-нибудь знает об одном? Поискав в Интернете, я не нашел ни такого алгоритма, ни алгоритма поиска наименьшего общего кратного или знаменателя двух чисел с плавающей запятой (только целых чисел).

Реализация Java:

Это последняя реализация, которую я буду использовать:

public class RatioTest
{
  public static String getRatio(double d1, double d2)//1.5, 3.25
  {
    while(Math.max(d1,d2) < Long.MAX_VALUE && d1 != (long)d1 && d2 != (long)d2)
    {
      d1 *= 10;//15 -> 150
      d2 *= 10;//32.5 -> 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) -> (150,175) -> (150,25) -> (125,25) -> (100,25) -> (75,25) -> (50,25) -> (25,25)
  {
    if (i1 == i2)
      return i1;//25
    if (i1 > i2)
      return getGCD(i1 - i2, i2);//(125,25) -> (100,25) -> (75,25) -> (50,25) -> (25,25)
    return getGCD(i1, i2 - i1);//(150,175) -> (150,25)
  }
}

• -> указывает следующий этап в вызове цикла или метода

Реализация Mystical как Java:

Хотя я не в конечном итоге использовал это, он более чем заслуживает признания, поэтому я перевел его на Java, чтобы я мог понять его:

import java.util.Stack;

public class RatioTest
{
    class Fraction{
        long num;
        long den;
        double val;
    };

    Fraction build_fraction(Stack<long> cf){
        long term = cf.size();
        long num = cf[term - 1];
        long den = 1;
        while (term-- > 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<long> 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 && new_error >= 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() < 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
    }
}

Еще кое-что:

Вышеупомянутый реализованный способ выполнения этого работает В ТЕОРИИ , однако, из-за ошибок округления с плавающей запятой это приводит к множеству неожиданных исключений, ошибок и выходных данных. Ниже приведена практичная, надежная, но немного грязная реализация алгоритма нахождения соотношения (для вашего удобства Javadoc):

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 <tt>String</tt>
   * <h4>Examples:</h4>
   * <ul>
   * <li><tt>getRatio(0.5, 12)</tt><ul>
     *   <li>returns "<tt>24:1</tt>"</li></ul></li>
   * <li><tt>getRatio(3, 82.0625)</tt><ul>
   *   <li>returns "<tt>1313:48</tt>"</li></ul></li>
   * </ul>
   * @param d1 the first number of the ratio
   * @param d2 the second number of the ratio
   * @return the resulting ratio, in the format "<tt>X:Y</tt>"
   */
  public static strictfp String getRatio(double d1, double d2)
  {
    while(Math.max(d1,d2) < Long.MAX_VALUE && (!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;
      }
    }
  }


  /**
   * <b>Recursively</b> 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 > i2)
      return getGCDRec(i1 - i2, i2);
    return getGCDRec(i1, i2 - i1);
  }

  /**
   * <b>Iteratively</b> 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 < Short.MAX_VALUE &&  i1 != i2; i++)
    {
      while (i1 > i2)
        i1 = i1 - i2;
      while (i2 > i1)
        i2 = i2 - i1;
    }
      return i1;
  }

  /**
   * Calculates and returns whether <tt>d1</tt> is close to <tt>d2</tt>
   * <h4>Examples:</h4>
   * <ul>
   * <li><tt>d1 == 5</tt>, <tt>d2 == 5</tt>
   *   <ul><li>returns <tt>true</tt></li></ul></li>
   * <li><tt>d1 == 5.0001</tt>, <tt>d2 == 5</tt>
   *   <ul><li>returns <tt>true</tt></li></ul></li>
   * <li><tt>d1 == 5</tt>, <tt>d2 == 5.0001</tt>
   *   <ul><li>returns <tt>true</tt></li></ul></li>
   * <li><tt>d1 == 5.24999</tt>, <tt>d2 == 5.25</tt>
   *   <ul><li>returns <tt>true</tt></li></ul></li>
   * <li><tt>d1 == 5.25</tt>, <tt>d2 == 5.24999</tt>
   *   <ul><li>returns <tt>true</tt></li></ul></li>
   * <li><tt>d1 == 5</tt>, <tt>d2 == 5.1</tt>
   *   <ul><li>returns <tt>false</tt></li></ul></li>
   * </ul>
   * @param d1 the first number to compare for closeness
   * @param d2 the second number to compare for closeness
   * @return <tt>true</tt> 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 <tt>d1</tt> 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() >= o.length() && c < 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 (<tt>.</tt>) is the only one treated as such.<br/>
   * <h4>Examples:</h4>
   * <li><tt>extractDouble("123456.789")</tt> returns the double value of <tt>123456.789</tt></li>
   * <li><tt>extractDouble("1qw2e3rty4uiop[5a'6.p7u8&9")</tt> returns the double value of <tt>123456.789</tt></li>
   * <li><tt>extractDouble("123,456.7.8.9")</tt> returns the double value of <tt>123456.789</tt></li>
   * <li><tt>extractDouble("I have $9,862.39 in the bank.")</tt> returns the double value of <tt>9862.39</tt></li>
   * @param str The <tt>String</tt> from which to extract a <tt>double</tt>.
   * @return the <tt>double</tt> that has been found within the string, if any.
   * @throws NumberFormatException if <tt>str</tt> 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 < str.length(); i++)
        if (Character.isDigit(str.charAt(i)) || (str.charAt(i) == RAD_POI && r))
        {
          if (str.charAt(i) == RAD_POI && 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);
      }
    }
  }
}