// file Rational.java   ---    1/17/99   ---   rgl
// class to support rational number operations
public class Rational  {
   long numerator, denominator;
// constructors
   Rational()  {
      numerator = 0;
      denominator = 1;
      return;
      }
   Rational(long num)  {
      numerator = num;
      denominator = 1;
      return;
      }
   Rational(long num, long den)  {
      numerator = num;
      denominator = den;
      long gcd = computeGCD(numerator, denominator);
      numerator /= gcd;
      denominator /= gcd;
      if (numerator==0)
         denominator = 1;
      if (denominator==0)
         numerator = 1;
      return;
      }
   Rational(String rat)  {
      String cleanRat = rat.trim();
      int solidusLocation = cleanRat.indexOf('/');
      if (solidusLocation<0)  {  // there is no '/'
         numerator = Long.parseLong(cleanRat);
         denominator = 1;
         return;
         }
      else  {                    // there is a '/'
         numerator = Long.parseLong(cleanRat.substring(0,solidusLocation));
         denominator = Long.parseLong(cleanRat.substring(solidusLocation+1));
         long gcd = computeGCD(numerator, denominator);
         numerator /= gcd;
         denominator /= gcd;
         if (numerator==0)
            denominator = 1;
         if (denominator==0)
            numerator = 1;
         return;
         }
      }
// construct an approx (up to 1.0e-12) rational for a double x
   Rational(double x)  {
      final double eps = 1.0e-12;
      if (x==0.0)  {
         numerator = 0;
         denominator = 1;
         return;
         }
      if (Math.abs(x)>Long.MAX_VALUE ||
          Math.abs(x)<1/(double)Long.MAX_VALUE)  {  // NaN
         numerator = 0;
         denominator = 0;
         return;
         }
      int sgn = 1;
      if (x<0.0)  {
         sgn = -1;
         x = -x;
         }
      long intPart = (long)x;
      double z = x - intPart;
      if (z!=0)  {
         z = 1.0/z;
         long a = (long)z;
         z = z - a;
         long prevNum = 0;
         long num = 1;
         long prevDen = 1;
         long den = a;
         long tmp;
         double approxAns = ((double)den*intPart + num)/den;
         while (Math.abs((x-approxAns)/x) >= eps)  {
            z = 1.0/z;
            a = (long)z;
            z = z - a;
            // deal with too-big numbers:
            if ((double)a*num+prevNum>Long.MAX_VALUE ||
                (double)a*den+prevDen>Long.MAX_VALUE)
               break;
            tmp = a*num + prevNum;
            prevNum = num;
            num = tmp;
            tmp = a*den + prevDen;
            prevDen = den;
            den = tmp;
            approxAns = ((double)den*intPart + num)/den;
            }
         numerator = sgn*(den*intPart + num);
         denominator = den;
         return;
         }
      else  {                    // is integer
         numerator = sgn*intPart;
         denominator = 1;
         return;
         }
      }
// construct an approx (up to eps) rational for a double x
   Rational(double x, double eps)  {
      if (x==0.0)  {
         numerator = 0;
         denominator = 1;
         return;
         }
      if (Math.abs(x)>Long.MAX_VALUE ||
          Math.abs(x)<1/(double)Long.MAX_VALUE)  {  // NaN
         numerator = 0;
         denominator = 0;
         return;
         }
      int sgn = 1;
      if (x<0.0)  {
         sgn = -1;
         x = -x;
         }
      long intPart = (long)x;
      double z = x - intPart;
      if (z!=0)  {
         z = 1.0/z;
         long a = (long)z;
         z = z - a;
         long prevNum = 0;
         long num = 1;
         long prevDen = 1;
         long den = a;
         long tmp;
         double approxAns = ((double)den*intPart + num)/den;
         while (Math.abs((x-approxAns)/x) >= eps)  {
            z = 1.0/z;
            a = (long)z;
            z = z - a;
            // deal with too-big numbers:
            if ((double)a*num+prevNum>Long.MAX_VALUE ||
                (double)a*den+prevDen>Long.MAX_VALUE)
               break;
            tmp = a*num + prevNum;
            prevNum = num;
            num = tmp;
            tmp = a*den + prevDen;
            prevDen = den;
            den = tmp;
            approxAns = ((double)den*intPart + num)/den;
            }
         numerator = sgn*(den*intPart + num);
         denominator = den;
         return;
         }
      else  {                    // is integer
         numerator = sgn*intPart;
         denominator = 1;
         return;
         }
      }
// other methods:
//    private GCD
   private static long computeGCD(long x, long y)  {
      x = (x<0 ? -x : x);
      y = (y<0 ? -y : y);
      long r;
      while (y>0)  {
         r = x%y;
         x = y;
         y = r;
         }
      return x;
      }
//    operations
   public Rational plus(Rational b)  {
      long num = numerator*b.denominator + b.numerator*denominator;
      long den = denominator*b.denominator;
      long gcd = computeGCD(num, den);
      return new Rational(num/gcd, den/gcd);
      }
   public Rational minus(Rational b)  {
      long num = numerator*b.denominator - b.numerator*denominator;
      long den = denominator*b.denominator;
      long gcd = computeGCD(num, den);
      return new Rational(num/gcd, den/gcd);
      }
   public Rational times(Rational b)  {
      long num = numerator*b.numerator;
      long den = denominator*b.denominator;
      long gcd = computeGCD(num, den);
      return new Rational(num/gcd, den/gcd);
      }
   public Rational quotient(Rational b)  {
      long num = numerator*b.denominator;
      long den = denominator*b.numerator;
      if (den<0)  {
         num = -num;
         den = -den;
         }
      long gcd = computeGCD(num, den);
      return new Rational(num/gcd, den/gcd);
      }
   public Rational reciprocal()  {
      long den = numerator;
      long num = denominator;
      if (den<0)  {
         num = -num;
         den = -den;
         }
      return new Rational(num, den);
      }
// to allow string conversion
   public String toString()  {
      if (denominator==0)  {
         if (numerator==0)
            return "NaN";
         else if (numerator<0)
            return "-Infinity";
         else                  // numerator>0
            return "Infinity";
         }
      if (denominator==1)
         return Long.toString(numerator);
      return Long.toString(numerator) + "/" + Long.toString(denominator);
      }
//    equality test
   public boolean equals(Rational b)  {
      return numerator==b.numerator && denominator==b.denominator;
      }
//    value as a double
   public double doubleValue()  {
      return (double)numerator/denominator;
      }
   }