RAT Algorithmus

Der RAT-Algorithmus wandelt einen double-Wert, durch ein Näherungsverfahren in einen Bruch um. Z.B. rat(pi) ergibt 3 + 1/(7 + 1/16) = 355/113.

The RAT algorithm converts a double value into a fraction value. This is done by interpolation.

/**
 * Rational Fraction Algorithm to convert double values
 * into fractions by the continous fraction algorithm
 *
 * rat(pi) = 3 + 1/(7 + 1/16) = 355/113
 * rat(e) = 3 + 1/(-4 + 1/(2 + 1/(5 + 1/(-2 + 1/(-7)))))
 *        = 1457/536
 *
 * @return point x / y fraction
 */
public class RationalFractionApproximation {
       public Point rat(double v) {
              double deviation = 0.000001 * Math.abs(v);             

              double v_start = v;

              int n_akt = 1;
              int n_alt = 0;

              int d_akt = 0;
              int d_alt = 1;

              int d = 0;

              while (true) {
                     d = (int) Math.round(v);
                     v = v - d;

                     int d_tmp = d_akt;
                     int n_tmp = n_akt;

                     d_akt = d * d_akt + d_alt;
                     n_akt = d * n_akt + n_alt;

                     d_alt = d_tmp;
                     n_alt = n_tmp;

                     double tmp = (double)n_akt / (double)d_akt - (double)v_start;
                     if ((v == 0) || (Math.abs(tmp) <= deviation)) {
                           break;
                     }

                     v = 1 / v;
              }

              int x = (int)(n_akt / Math.signum(d_akt));
              int y = Math.abs(d_akt);

              Point p = new Point(x, y);
              return p;
       }
}

Werbung



comments powered by Disqus

Copyright Dunkel & Iwer GbR | Datenschutzerklärung | Impressum