Coverage Report - org.apache.commons.lang3.math.Fraction
 
Classes in this File Line Coverage Branch Coverage Complexity
Fraction
97%
259/265
91%
180/196
5,353
 
 1  
 /*
 2  
  * Licensed to the Apache Software Foundation (ASF) under one or more
 3  
  * contributor license agreements.  See the NOTICE file distributed with
 4  
  * this work for additional information regarding copyright ownership.
 5  
  * The ASF licenses this file to You under the Apache License, Version 2.0
 6  
  * (the "License"); you may not use this file except in compliance with
 7  
  * the License.  You may obtain a copy of the License at
 8  
  * 
 9  
  *      http://www.apache.org/licenses/LICENSE-2.0
 10  
  * 
 11  
  * Unless required by applicable law or agreed to in writing, software
 12  
  * distributed under the License is distributed on an "AS IS" BASIS,
 13  
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 14  
  * See the License for the specific language governing permissions and
 15  
  * limitations under the License.
 16  
  */
 17  
 package org.apache.commons.lang3.math;
 18  
 
 19  
 import java.math.BigInteger;
 20  
 
 21  
 /**
 22  
  * <p><code>Fraction</code> is a <code>Number</code> implementation that
 23  
  * stores fractions accurately.</p>
 24  
  *
 25  
  * <p>This class is immutable, and interoperable with most methods that accept
 26  
  * a <code>Number</code>.</p>
 27  
  *
 28  
  * <p>Note that this class is intended for common use cases, it is <i>int</i>
 29  
  * based and thus suffers from various overflow issues. For a BigInteger based 
 30  
  * equivalent, please see the Commons Math BigFraction class. </p>
 31  
  *
 32  
  * @since 2.0
 33  
  * @version $Id: Fraction.java 1583482 2014-03-31 22:54:57Z niallp $
 34  
  */
 35  0
 public final class Fraction extends Number implements Comparable<Fraction> {
 36  
 
 37  
     /**
 38  
      * Required for serialization support. Lang version 2.0.
 39  
      * 
 40  
      * @see java.io.Serializable
 41  
      */
 42  
     private static final long serialVersionUID = 65382027393090L;
 43  
 
 44  
     /**
 45  
      * <code>Fraction</code> representation of 0.
 46  
      */
 47  1
     public static final Fraction ZERO = new Fraction(0, 1);
 48  
     /**
 49  
      * <code>Fraction</code> representation of 1.
 50  
      */
 51  1
     public static final Fraction ONE = new Fraction(1, 1);
 52  
     /**
 53  
      * <code>Fraction</code> representation of 1/2.
 54  
      */
 55  1
     public static final Fraction ONE_HALF = new Fraction(1, 2);
 56  
     /**
 57  
      * <code>Fraction</code> representation of 1/3.
 58  
      */
 59  1
     public static final Fraction ONE_THIRD = new Fraction(1, 3);
 60  
     /**
 61  
      * <code>Fraction</code> representation of 2/3.
 62  
      */
 63  1
     public static final Fraction TWO_THIRDS = new Fraction(2, 3);
 64  
     /**
 65  
      * <code>Fraction</code> representation of 1/4.
 66  
      */
 67  1
     public static final Fraction ONE_QUARTER = new Fraction(1, 4);
 68  
     /**
 69  
      * <code>Fraction</code> representation of 2/4.
 70  
      */
 71  1
     public static final Fraction TWO_QUARTERS = new Fraction(2, 4);
 72  
     /**
 73  
      * <code>Fraction</code> representation of 3/4.
 74  
      */
 75  1
     public static final Fraction THREE_QUARTERS = new Fraction(3, 4);
 76  
     /**
 77  
      * <code>Fraction</code> representation of 1/5.
 78  
      */
 79  1
     public static final Fraction ONE_FIFTH = new Fraction(1, 5);
 80  
     /**
 81  
      * <code>Fraction</code> representation of 2/5.
 82  
      */
 83  1
     public static final Fraction TWO_FIFTHS = new Fraction(2, 5);
 84  
     /**
 85  
      * <code>Fraction</code> representation of 3/5.
 86  
      */
 87  1
     public static final Fraction THREE_FIFTHS = new Fraction(3, 5);
 88  
     /**
 89  
      * <code>Fraction</code> representation of 4/5.
 90  
      */
 91  1
     public static final Fraction FOUR_FIFTHS = new Fraction(4, 5);
 92  
 
 93  
 
 94  
     /**
 95  
      * The numerator number part of the fraction (the three in three sevenths).
 96  
      */
 97  
     private final int numerator;
 98  
     /**
 99  
      * The denominator number part of the fraction (the seven in three sevenths).
 100  
      */
 101  
     private final int denominator;
 102  
 
 103  
     /**
 104  
      * Cached output hashCode (class is immutable).
 105  
      */
 106  199512
     private transient int hashCode = 0;
 107  
     /**
 108  
      * Cached output toString (class is immutable).
 109  
      */
 110  199512
     private transient String toString = null;
 111  
     /**
 112  
      * Cached output toProperString (class is immutable).
 113  
      */
 114  199512
     private transient String toProperString = null;
 115  
 
 116  
     /**
 117  
      * <p>Constructs a <code>Fraction</code> instance with the 2 parts
 118  
      * of a fraction Y/Z.</p>
 119  
      *
 120  
      * @param numerator  the numerator, for example the three in 'three sevenths'
 121  
      * @param denominator  the denominator, for example the seven in 'three sevenths'
 122  
      */
 123  
     private Fraction(final int numerator, final int denominator) {
 124  199512
         super();
 125  199512
         this.numerator = numerator;
 126  199512
         this.denominator = denominator;
 127  199512
     }
 128  
 
 129  
     /**
 130  
      * <p>Creates a <code>Fraction</code> instance with the 2 parts
 131  
      * of a fraction Y/Z.</p>
 132  
      *
 133  
      * <p>Any negative signs are resolved to be on the numerator.</p>
 134  
      *
 135  
      * @param numerator  the numerator, for example the three in 'three sevenths'
 136  
      * @param denominator  the denominator, for example the seven in 'three sevenths'
 137  
      * @return a new fraction instance
 138  
      * @throws ArithmeticException if the denominator is <code>zero</code>
 139  
      * or the denominator is {@code negative} and the numerator is {@code Integer#MIN_VALUE}
 140  
      */
 141  
     public static Fraction getFraction(int numerator, int denominator) {
 142  170
         if (denominator == 0) {
 143  3
             throw new ArithmeticException("The denominator must not be zero");
 144  
         }
 145  167
         if (denominator < 0) {
 146  9
             if (numerator==Integer.MIN_VALUE ||
 147  
                     denominator==Integer.MIN_VALUE) {
 148  2
                 throw new ArithmeticException("overflow: can't negate");
 149  
             }
 150  7
             numerator = -numerator;
 151  7
             denominator = -denominator;
 152  
         }
 153  165
         return new Fraction(numerator, denominator);
 154  
     }
 155  
 
 156  
     /**
 157  
      * <p>Creates a <code>Fraction</code> instance with the 3 parts
 158  
      * of a fraction X Y/Z.</p>
 159  
      *
 160  
      * <p>The negative sign must be passed in on the whole number part.</p>
 161  
      *
 162  
      * @param whole  the whole number, for example the one in 'one and three sevenths'
 163  
      * @param numerator  the numerator, for example the three in 'one and three sevenths'
 164  
      * @param denominator  the denominator, for example the seven in 'one and three sevenths'
 165  
      * @return a new fraction instance
 166  
      * @throws ArithmeticException if the denominator is <code>zero</code>
 167  
      * @throws ArithmeticException if the denominator is negative
 168  
      * @throws ArithmeticException if the numerator is negative
 169  
      * @throws ArithmeticException if the resulting numerator exceeds 
 170  
      *  <code>Integer.MAX_VALUE</code>
 171  
      */
 172  
     public static Fraction getFraction(final int whole, final int numerator, final int denominator) {
 173  35
         if (denominator == 0) {
 174  3
             throw new ArithmeticException("The denominator must not be zero");
 175  
         }
 176  32
         if (denominator < 0) {
 177  6
             throw new ArithmeticException("The denominator must not be negative");
 178  
         }
 179  26
         if (numerator < 0) {
 180  1
             throw new ArithmeticException("The numerator must not be negative");
 181  
         }
 182  
         long numeratorValue;
 183  25
         if (whole < 0) {
 184  13
             numeratorValue = whole * (long)denominator - numerator;
 185  
         } else {
 186  12
             numeratorValue = whole * (long)denominator + numerator;
 187  
         }
 188  25
         if (numeratorValue < Integer.MIN_VALUE ||
 189  
                 numeratorValue > Integer.MAX_VALUE)  {
 190  4
             throw new ArithmeticException("Numerator too large to represent as an Integer.");
 191  
         }
 192  21
         return new Fraction((int) numeratorValue, denominator);
 193  
     }
 194  
 
 195  
     /**
 196  
      * <p>Creates a reduced <code>Fraction</code> instance with the 2 parts
 197  
      * of a fraction Y/Z.</p>
 198  
      *
 199  
      * <p>For example, if the input parameters represent 2/4, then the created
 200  
      * fraction will be 1/2.</p>
 201  
      *
 202  
      * <p>Any negative signs are resolved to be on the numerator.</p>
 203  
      *
 204  
      * @param numerator  the numerator, for example the three in 'three sevenths'
 205  
      * @param denominator  the denominator, for example the seven in 'three sevenths'
 206  
      * @return a new fraction instance, with the numerator and denominator reduced
 207  
      * @throws ArithmeticException if the denominator is <code>zero</code>
 208  
      */
 209  
     public static Fraction getReducedFraction(int numerator, int denominator) {
 210  199276
         if (denominator == 0) {
 211  3
             throw new ArithmeticException("The denominator must not be zero");
 212  
         }
 213  199273
         if (numerator==0) {
 214  5
             return ZERO; // normalize zero.
 215  
         }
 216  
         // allow 2^k/-2^31 as a valid fraction (where k>0)
 217  199268
         if (denominator==Integer.MIN_VALUE && (numerator&1)==0) {
 218  1
             numerator/=2; denominator/=2;
 219  
         }
 220  199268
         if (denominator < 0) {
 221  4
             if (numerator==Integer.MIN_VALUE ||
 222  
                     denominator==Integer.MIN_VALUE) {
 223  1
                 throw new ArithmeticException("overflow: can't negate");
 224  
             }
 225  3
             numerator = -numerator;
 226  3
             denominator = -denominator;
 227  
         }
 228  
         // simplify fraction.
 229  199267
         final int gcd = greatestCommonDivisor(numerator, denominator);
 230  199267
         numerator /= gcd;
 231  199267
         denominator /= gcd;
 232  199267
         return new Fraction(numerator, denominator);
 233  
     }
 234  
 
 235  
     /**
 236  
      * <p>Creates a <code>Fraction</code> instance from a <code>double</code> value.</p>
 237  
      *
 238  
      * <p>This method uses the <a href="http://archives.math.utk.edu/articles/atuyl/confrac/">
 239  
      *  continued fraction algorithm</a>, computing a maximum of
 240  
      *  25 convergents and bounding the denominator by 10,000.</p>
 241  
      *
 242  
      * @param value  the double value to convert
 243  
      * @return a new fraction instance that is close to the value
 244  
      * @throws ArithmeticException if <code>|value| &gt; Integer.MAX_VALUE</code> 
 245  
      *  or <code>value = NaN</code>
 246  
      * @throws ArithmeticException if the calculated denominator is <code>zero</code>
 247  
      * @throws ArithmeticException if the the algorithm does not converge
 248  
      */
 249  
     public static Fraction getFraction(double value) {
 250  99584
         final int sign = value < 0 ? -1 : 1;
 251  99584
         value = Math.abs(value);
 252  99584
         if (value  > Integer.MAX_VALUE || Double.isNaN(value)) {
 253  4
             throw new ArithmeticException
 254  
                 ("The value must not be greater than Integer.MAX_VALUE or NaN");
 255  
         }
 256  99580
         final int wholeNumber = (int) value;
 257  99580
         value -= wholeNumber;
 258  
         
 259  99580
         int numer0 = 0;  // the pre-previous
 260  99580
         int denom0 = 1;  // the pre-previous
 261  99580
         int numer1 = 1;  // the previous
 262  99580
         int denom1 = 0;  // the previous
 263  99580
         int numer2 = 0;  // the current, setup in calculation
 264  99580
         int denom2 = 0;  // the current, setup in calculation
 265  99580
         int a1 = (int) value;
 266  99580
         int a2 = 0;
 267  99580
         double x1 = 1;
 268  99580
         double x2 = 0;
 269  99580
         double y1 = value - a1;
 270  99580
         double y2 = 0;
 271  99580
         double delta1, delta2 = Double.MAX_VALUE;
 272  
         double fraction;
 273  99580
         int i = 1;
 274  
 //        System.out.println("---");
 275  
         do {
 276  982446
             delta1 = delta2;
 277  982446
             a2 = (int) (x1 / y1);
 278  982446
             x2 = y1;
 279  982446
             y2 = x1 - a2 * y1;
 280  982446
             numer2 = a1 * numer1 + numer0;
 281  982446
             denom2 = a1 * denom1 + denom0;
 282  982446
             fraction = (double) numer2 / (double) denom2;
 283  982446
             delta2 = Math.abs(value - fraction);
 284  
 //            System.out.println(numer2 + " " + denom2 + " " + fraction + " " + delta2 + " " + y1);
 285  982446
             a1 = a2;
 286  982446
             x1 = x2;
 287  982446
             y1 = y2;
 288  982446
             numer0 = numer1;
 289  982446
             denom0 = denom1;
 290  982446
             numer1 = numer2;
 291  982446
             denom1 = denom2;
 292  982446
             i++;
 293  
 //            System.out.println(">>" + delta1 +" "+ delta2+" "+(delta1 > delta2)+" "+i+" "+denom2);
 294  982446
         } while (delta1 > delta2 && denom2 <= 10000 && denom2 > 0 && i < 25);
 295  99580
         if (i == 25) {
 296  0
             throw new ArithmeticException("Unable to convert double to fraction");
 297  
         }
 298  99580
         return getReducedFraction((numer0 + wholeNumber * denom0) * sign, denom0);
 299  
     }
 300  
 
 301  
     /**
 302  
      * <p>Creates a Fraction from a <code>String</code>.</p>
 303  
      *
 304  
      * <p>The formats accepted are:</p>
 305  
      *
 306  
      * <ol>
 307  
      *  <li><code>double</code> String containing a dot</li>
 308  
      *  <li>'X Y/Z'</li>
 309  
      *  <li>'Y/Z'</li>
 310  
      *  <li>'X' (a simple whole number)</li>
 311  
      * </ol>
 312  
      * <p>and a .</p>
 313  
      *
 314  
      * @param str  the string to parse, must not be <code>null</code>
 315  
      * @return the new <code>Fraction</code> instance
 316  
      * @throws IllegalArgumentException if the string is <code>null</code>
 317  
      * @throws NumberFormatException if the number format is invalid
 318  
      */
 319  
     public static Fraction getFraction(String str) {
 320  30
         if (str == null) {
 321  1
             throw new IllegalArgumentException("The string must not be null");
 322  
         }
 323  
         // parse double format
 324  29
         int pos = str.indexOf('.');
 325  29
         if (pos >= 0) {
 326  6
             return getFraction(Double.parseDouble(str));
 327  
         }
 328  
 
 329  
         // parse X Y/Z format
 330  23
         pos = str.indexOf(' ');
 331  23
         if (pos > 0) {
 332  10
             final int whole = Integer.parseInt(str.substring(0, pos));
 333  9
             str = str.substring(pos + 1);
 334  9
             pos = str.indexOf('/');
 335  9
             if (pos < 0) {
 336  2
                 throw new NumberFormatException("The fraction could not be parsed as the format X Y/Z");
 337  
             } else {
 338  7
                 final int numer = Integer.parseInt(str.substring(0, pos));
 339  6
                 final int denom = Integer.parseInt(str.substring(pos + 1));
 340  6
                 return getFraction(whole, numer, denom);
 341  
             }
 342  
         }
 343  
 
 344  
         // parse Y/Z format
 345  13
         pos = str.indexOf('/');
 346  13
         if (pos < 0) {
 347  
             // simple whole number
 348  3
             return getFraction(Integer.parseInt(str), 1);
 349  
         } else {
 350  10
             final int numer = Integer.parseInt(str.substring(0, pos));
 351  8
             final int denom = Integer.parseInt(str.substring(pos + 1));
 352  6
             return getFraction(numer, denom);
 353  
         }
 354  
     }
 355  
 
 356  
     // Accessors
 357  
     //-------------------------------------------------------------------
 358  
 
 359  
     /**
 360  
      * <p>Gets the numerator part of the fraction.</p>
 361  
      *
 362  
      * <p>This method may return a value greater than the denominator, an
 363  
      * improper fraction, such as the seven in 7/4.</p>
 364  
      *
 365  
      * @return the numerator fraction part
 366  
      */
 367  
     public int getNumerator() {
 368  199294
         return numerator;
 369  
     }
 370  
 
 371  
     /**
 372  
      * <p>Gets the denominator part of the fraction.</p>
 373  
      *
 374  
      * @return the denominator fraction part
 375  
      */
 376  
     public int getDenominator() {
 377  199292
         return denominator;
 378  
     }
 379  
 
 380  
     /**
 381  
      * <p>Gets the proper numerator, always positive.</p>
 382  
      *
 383  
      * <p>An improper fraction 7/4 can be resolved into a proper one, 1 3/4.
 384  
      * This method returns the 3 from the proper fraction.</p>
 385  
      *
 386  
      * <p>If the fraction is negative such as -7/4, it can be resolved into
 387  
      * -1 3/4, so this method returns the positive proper numerator, 3.</p>
 388  
      *
 389  
      * @return the numerator fraction part of a proper fraction, always positive
 390  
      */
 391  
     public int getProperNumerator() {
 392  9
         return Math.abs(numerator % denominator);
 393  
     }
 394  
 
 395  
     /**
 396  
      * <p>Gets the proper whole part of the fraction.</p>
 397  
      *
 398  
      * <p>An improper fraction 7/4 can be resolved into a proper one, 1 3/4.
 399  
      * This method returns the 1 from the proper fraction.</p>
 400  
      *
 401  
      * <p>If the fraction is negative such as -7/4, it can be resolved into
 402  
      * -1 3/4, so this method returns the positive whole part -1.</p>
 403  
      *
 404  
      * @return the whole fraction part of a proper fraction, that includes the sign
 405  
      */
 406  
     public int getProperWhole() {
 407  9
         return numerator / denominator;
 408  
     }
 409  
 
 410  
     // Number methods
 411  
     //-------------------------------------------------------------------
 412  
 
 413  
     /**
 414  
      * <p>Gets the fraction as an <code>int</code>. This returns the whole number
 415  
      * part of the fraction.</p>
 416  
      *
 417  
      * @return the whole number fraction part
 418  
      */
 419  
     @Override
 420  
     public int intValue() {
 421  1
         return numerator / denominator;
 422  
     }
 423  
 
 424  
     /**
 425  
      * <p>Gets the fraction as a <code>long</code>. This returns the whole number
 426  
      * part of the fraction.</p>
 427  
      *
 428  
      * @return the whole number fraction part
 429  
      */
 430  
     @Override
 431  
     public long longValue() {
 432  1
         return (long) numerator / denominator;
 433  
     }
 434  
 
 435  
     /**
 436  
      * <p>Gets the fraction as a <code>float</code>. This calculates the fraction
 437  
      * as the numerator divided by denominator.</p>
 438  
      *
 439  
      * @return the fraction as a <code>float</code>
 440  
      */
 441  
     @Override
 442  
     public float floatValue() {
 443  1
         return (float) numerator / (float) denominator;
 444  
     }
 445  
 
 446  
     /**
 447  
      * <p>Gets the fraction as a <code>double</code>. This calculates the fraction
 448  
      * as the numerator divided by denominator.</p>
 449  
      *
 450  
      * @return the fraction as a <code>double</code>
 451  
      */
 452  
     @Override
 453  
     public double doubleValue() {
 454  1
         return (double) numerator / (double) denominator;
 455  
     }
 456  
 
 457  
     // Calculations
 458  
     //-------------------------------------------------------------------
 459  
 
 460  
     /**
 461  
      * <p>Reduce the fraction to the smallest values for the numerator and
 462  
      * denominator, returning the result.</p>
 463  
      * 
 464  
      * <p>For example, if this fraction represents 2/4, then the result
 465  
      * will be 1/2.</p>
 466  
      *
 467  
      * @return a new reduced fraction instance, or this if no simplification possible
 468  
      */
 469  
     public Fraction reduce() {
 470  8
         if (numerator == 0) {
 471  2
             return equals(ZERO) ? this : ZERO;
 472  
         }
 473  6
         final int gcd = greatestCommonDivisor(Math.abs(numerator), denominator);
 474  6
         if (gcd == 1) {
 475  4
             return this;
 476  
         }
 477  2
         return Fraction.getFraction(numerator / gcd, denominator / gcd);
 478  
     }
 479  
 
 480  
     /**
 481  
      * <p>Gets a fraction that is the inverse (1/fraction) of this one.</p>
 482  
      * 
 483  
      * <p>The returned fraction is not reduced.</p>
 484  
      *
 485  
      * @return a new fraction instance with the numerator and denominator
 486  
      *         inverted.
 487  
      * @throws ArithmeticException if the fraction represents zero.
 488  
      */
 489  
     public Fraction invert() {
 490  23
         if (numerator == 0) {
 491  3
             throw new ArithmeticException("Unable to invert zero.");
 492  
         }
 493  20
         if (numerator==Integer.MIN_VALUE) {
 494  1
             throw new ArithmeticException("overflow: can't negate numerator");
 495  
         }
 496  19
         if (numerator<0) {
 497  3
             return new Fraction(-denominator, -numerator);
 498  
         } else {
 499  16
             return new Fraction(denominator, numerator);
 500  
         }
 501  
     }
 502  
 
 503  
     /**
 504  
      * <p>Gets a fraction that is the negative (-fraction) of this one.</p>
 505  
      *
 506  
      * <p>The returned fraction is not reduced.</p>
 507  
      *
 508  
      * @return a new fraction instance with the opposite signed numerator
 509  
      */
 510  
     public Fraction negate() {
 511  
         // the positive range is one smaller than the negative range of an int.
 512  11
         if (numerator==Integer.MIN_VALUE) {
 513  2
             throw new ArithmeticException("overflow: too large to negate");
 514  
         }
 515  9
         return new Fraction(-numerator, denominator);
 516  
     }
 517  
 
 518  
     /**
 519  
      * <p>Gets a fraction that is the positive equivalent of this one.</p>
 520  
      * <p>More precisely: <code>(fraction &gt;= 0 ? this : -fraction)</code></p>
 521  
      *
 522  
      * <p>The returned fraction is not reduced.</p>
 523  
      *
 524  
      * @return <code>this</code> if it is positive, or a new positive fraction
 525  
      *  instance with the opposite signed numerator
 526  
      */
 527  
     public Fraction abs() {
 528  5
         if (numerator >= 0) {
 529  2
             return this;
 530  
         }
 531  3
         return negate();
 532  
     }
 533  
 
 534  
     /**
 535  
      * <p>Gets a fraction that is raised to the passed in power.</p>
 536  
      *
 537  
      * <p>The returned fraction is in reduced form.</p>
 538  
      *
 539  
      * @param power  the power to raise the fraction to
 540  
      * @return <code>this</code> if the power is one, <code>ONE</code> if the power
 541  
      * is zero (even if the fraction equals ZERO) or a new fraction instance 
 542  
      * raised to the appropriate power
 543  
      * @throws ArithmeticException if the resulting numerator or denominator exceeds
 544  
      *  <code>Integer.MAX_VALUE</code>
 545  
      */
 546  
     public Fraction pow(final int power) {
 547  101
         if (power == 1) {
 548  19
             return this;
 549  82
         } else if (power == 0) {
 550  3
             return ONE;
 551  79
         } else if (power < 0) {
 552  8
             if (power==Integer.MIN_VALUE) { // MIN_VALUE can't be negated.
 553  2
                 return this.invert().pow(2).pow(-(power/2));
 554  
             }
 555  6
             return this.invert().pow(-power);
 556  
         } else {
 557  71
             final Fraction f = this.multiplyBy(this);
 558  68
             if (power % 2 == 0) { // if even...
 559  36
                 return f.pow(power/2);
 560  
             } else { // if odd...
 561  32
                 return f.pow(power/2).multiplyBy(this);
 562  
             }
 563  
         }
 564  
     }
 565  
 
 566  
     /**
 567  
      * <p>Gets the greatest common divisor of the absolute value of
 568  
      * two numbers, using the "binary gcd" method which avoids
 569  
      * division and modulo operations.  See Knuth 4.5.2 algorithm B.
 570  
      * This algorithm is due to Josef Stein (1961).</p>
 571  
      *
 572  
      * @param u  a non-zero number
 573  
      * @param v  a non-zero number
 574  
      * @return the greatest common divisor, never zero
 575  
      */
 576  
     private static int greatestCommonDivisor(int u, int v) {
 577  
         // From Commons Math:
 578  199549
         if (u == 0 || v == 0) {
 579  0
             if (u == Integer.MIN_VALUE || v == Integer.MIN_VALUE) {
 580  0
                 throw new ArithmeticException("overflow: gcd is 2^31");
 581  
             }
 582  0
             return Math.abs(u) + Math.abs(v);
 583  
         }
 584  
         //if either operand is abs 1, return 1:
 585  199549
         if (Math.abs(u) == 1 || Math.abs(v) == 1) {
 586  1000
             return 1;
 587  
         }
 588  
         // keep u and v negative, as negative integers range down to
 589  
         // -2^31, while positive numbers can only be as large as 2^31-1
 590  
         // (i.e. we can't necessarily negate a negative number without
 591  
         // overflow)
 592  198549
         if (u>0) { u=-u; } // make u negative
 593  198549
         if (v>0) { v=-v; } // make v negative
 594  
         // B1. [Find power of 2]
 595  198549
         int k=0;
 596  200274
         while ((u&1)==0 && (v&1)==0 && k<31) { // while u and v are both even...
 597  1725
             u/=2; v/=2; k++; // cast out twos.
 598  
         }
 599  198549
         if (k==31) {
 600  0
             throw new ArithmeticException("overflow: gcd is 2^31");
 601  
         }
 602  
         // B2. Initialize: u and v have been divided by 2^k and at least
 603  
         //     one is odd.
 604  198549
         int t = (u&1)==1 ? v : -(u/2)/*B3*/;
 605  
         // t negative: u was odd, v may be even (t replaces v)
 606  
         // t positive: u was even, v is odd (t replaces u)
 607  
         do {
 608  
             /* assert u<0 && v<0; */
 609  
             // B4/B3: cast out twos from t.
 610  3303752
             while ((t&1)==0) { // while t is even..
 611  1498661
                 t/=2; // cast out twos
 612  
             }
 613  
             // B5 [reset max(u,v)]
 614  1805091
             if (t>0) {
 615  821671
                 u = -t;
 616  
             } else {
 617  983420
                 v = t;
 618  
             }
 619  
             // B6/B3. at this point both u and v should be odd.
 620  1805091
             t = (v - u)/2;
 621  
             // |u| larger: t positive (replace u)
 622  
             // |v| larger: t negative (replace v)
 623  1805091
         } while (t!=0);
 624  198549
         return -u*(1<<k); // gcd is u*2^k
 625  
     }
 626  
 
 627  
     // Arithmetic
 628  
     //-------------------------------------------------------------------
 629  
 
 630  
     /** 
 631  
      * Multiply two integers, checking for overflow.
 632  
      * 
 633  
      * @param x a factor
 634  
      * @param y a factor
 635  
      * @return the product <code>x*y</code>
 636  
      * @throws ArithmeticException if the result can not be represented as
 637  
      *                             an int
 638  
      */
 639  
     private static int mulAndCheck(final int x, final int y) {
 640  143
         final long m = (long)x*(long)y;
 641  143
         if (m < Integer.MIN_VALUE ||
 642  
             m > Integer.MAX_VALUE) {
 643  3
             throw new ArithmeticException("overflow: mul");
 644  
         }
 645  140
         return (int)m;
 646  
     }
 647  
     
 648  
     /**
 649  
      *  Multiply two non-negative integers, checking for overflow.
 650  
      * 
 651  
      * @param x a non-negative factor
 652  
      * @param y a non-negative factor
 653  
      * @return the product <code>x*y</code>
 654  
      * @throws ArithmeticException if the result can not be represented as
 655  
      * an int
 656  
      */
 657  
     private static int mulPosAndCheck(final int x, final int y) {
 658  
         /* assert x>=0 && y>=0; */
 659  136
         final long m = (long)x*(long)y;
 660  136
         if (m > Integer.MAX_VALUE) {
 661  7
             throw new ArithmeticException("overflow: mulPos");
 662  
         }
 663  129
         return (int)m;
 664  
     }
 665  
     
 666  
     /** 
 667  
      * Add two integers, checking for overflow.
 668  
      * 
 669  
      * @param x an addend
 670  
      * @param y an addend
 671  
      * @return the sum <code>x+y</code>
 672  
      * @throws ArithmeticException if the result can not be represented as
 673  
      * an int
 674  
      */
 675  
     private static int addAndCheck(final int x, final int y) {
 676  7
         final long s = (long)x+(long)y;
 677  7
         if (s < Integer.MIN_VALUE ||
 678  
             s > Integer.MAX_VALUE) {
 679  3
             throw new ArithmeticException("overflow: add");
 680  
         }
 681  4
         return (int)s;
 682  
     }
 683  
     
 684  
     /** 
 685  
      * Subtract two integers, checking for overflow.
 686  
      * 
 687  
      * @param x the minuend
 688  
      * @param y the subtrahend
 689  
      * @return the difference <code>x-y</code>
 690  
      * @throws ArithmeticException if the result can not be represented as
 691  
      * an int
 692  
      */
 693  
     private static int subAndCheck(final int x, final int y) {
 694  6
         final long s = (long)x-(long)y;
 695  6
         if (s < Integer.MIN_VALUE ||
 696  
             s > Integer.MAX_VALUE) {
 697  2
             throw new ArithmeticException("overflow: add");
 698  
         }
 699  4
         return (int)s;
 700  
     }
 701  
     
 702  
     /**
 703  
      * <p>Adds the value of this fraction to another, returning the result in reduced form.
 704  
      * The algorithm follows Knuth, 4.5.1.</p>
 705  
      *
 706  
      * @param fraction  the fraction to add, must not be <code>null</code>
 707  
      * @return a <code>Fraction</code> instance with the resulting values
 708  
      * @throws IllegalArgumentException if the fraction is <code>null</code>
 709  
      * @throws ArithmeticException if the resulting numerator or denominator exceeds
 710  
      *  <code>Integer.MAX_VALUE</code>
 711  
      */
 712  
     public Fraction add(final Fraction fraction) {
 713  19
         return addSub(fraction, true /* add */);
 714  
     }
 715  
 
 716  
     /**
 717  
      * <p>Subtracts the value of another fraction from the value of this one, 
 718  
      * returning the result in reduced form.</p>
 719  
      *
 720  
      * @param fraction  the fraction to subtract, must not be <code>null</code>
 721  
      * @return a <code>Fraction</code> instance with the resulting values
 722  
      * @throws IllegalArgumentException if the fraction is <code>null</code>
 723  
      * @throws ArithmeticException if the resulting numerator or denominator
 724  
      *   cannot be represented in an <code>int</code>.
 725  
      */
 726  
     public Fraction subtract(final Fraction fraction) {
 727  17
         return addSub(fraction, false /* subtract */);
 728  
     }
 729  
 
 730  
     /** 
 731  
      * Implement add and subtract using algorithm described in Knuth 4.5.1.
 732  
      * 
 733  
      * @param fraction the fraction to subtract, must not be <code>null</code>
 734  
      * @param isAdd true to add, false to subtract
 735  
      * @return a <code>Fraction</code> instance with the resulting values
 736  
      * @throws IllegalArgumentException if the fraction is <code>null</code>
 737  
      * @throws ArithmeticException if the resulting numerator or denominator
 738  
      *   cannot be represented in an <code>int</code>.
 739  
      */
 740  
     private Fraction addSub(final Fraction fraction, final boolean isAdd) {
 741  36
         if (fraction == null) {
 742  2
             throw new IllegalArgumentException("The fraction must not be null");
 743  
         }
 744  
         // zero is identity for addition.
 745  34
         if (numerator == 0) {
 746  3
             return isAdd ? fraction : fraction.negate();
 747  
         }
 748  31
         if (fraction.numerator == 0) {
 749  2
             return this;
 750  
         }     
 751  
         // if denominators are randomly distributed, d1 will be 1 about 61%
 752  
         // of the time.
 753  29
         final int d1 = greatestCommonDivisor(denominator, fraction.denominator);
 754  29
         if (d1==1) {
 755  
             // result is ( (u*v' +/- u'v) / u'v')
 756  13
             final int uvp = mulAndCheck(numerator, fraction.denominator);
 757  13
             final int upv = mulAndCheck(fraction.numerator, denominator);
 758  13
             return new Fraction
 759  
                 (isAdd ? addAndCheck(uvp, upv) : subAndCheck(uvp, upv),
 760  
                  mulPosAndCheck(denominator, fraction.denominator));
 761  
         }
 762  
         // the quantity 't' requires 65 bits of precision; see knuth 4.5.1
 763  
         // exercise 7.  we're going to use a BigInteger.
 764  
         // t = u(v'/d1) +/- v(u'/d1)
 765  16
         final BigInteger uvp = BigInteger.valueOf(numerator)
 766  
             .multiply(BigInteger.valueOf(fraction.denominator/d1));
 767  16
         final BigInteger upv = BigInteger.valueOf(fraction.numerator)
 768  
             .multiply(BigInteger.valueOf(denominator/d1));
 769  16
         final BigInteger t = isAdd ? uvp.add(upv) : uvp.subtract(upv);
 770  
         // but d2 doesn't need extra precision because
 771  
         // d2 = gcd(t,d1) = gcd(t mod d1, d1)
 772  16
         final int tmodd1 = t.mod(BigInteger.valueOf(d1)).intValue();
 773  16
         final int d2 = tmodd1==0?d1:greatestCommonDivisor(tmodd1, d1);
 774  
 
 775  
         // result is (t/d2) / (u'/d1)(v'/d2)
 776  16
         final BigInteger w = t.divide(BigInteger.valueOf(d2));
 777  16
         if (w.bitLength() > 31) {
 778  2
             throw new ArithmeticException
 779  
                 ("overflow: numerator too large after multiply");
 780  
         }
 781  14
         return new Fraction
 782  
             (w.intValue(),
 783  
              mulPosAndCheck(denominator/d1, fraction.denominator/d2));
 784  
     }
 785  
 
 786  
     /**
 787  
      * <p>Multiplies the value of this fraction by another, returning the 
 788  
      * result in reduced form.</p>
 789  
      *
 790  
      * @param fraction  the fraction to multiply by, must not be <code>null</code>
 791  
      * @return a <code>Fraction</code> instance with the resulting values
 792  
      * @throws IllegalArgumentException if the fraction is <code>null</code>
 793  
      * @throws ArithmeticException if the resulting numerator or denominator exceeds
 794  
      *  <code>Integer.MAX_VALUE</code>
 795  
      */
 796  
     public Fraction multiplyBy(final Fraction fraction) {
 797  121
         if (fraction == null) {
 798  1
             throw new IllegalArgumentException("The fraction must not be null");
 799  
         }
 800  120
         if (numerator == 0 || fraction.numerator == 0) {
 801  3
             return ZERO;
 802  
         }
 803  
         // knuth 4.5.1
 804  
         // make sure we don't overflow unless the result *must* overflow.
 805  117
         final int d1 = greatestCommonDivisor(numerator, fraction.denominator);
 806  117
         final int d2 = greatestCommonDivisor(fraction.numerator, denominator);
 807  117
         return getReducedFraction
 808  
             (mulAndCheck(numerator/d1, fraction.numerator/d2),
 809  
              mulPosAndCheck(denominator/d2, fraction.denominator/d1));
 810  
     }
 811  
 
 812  
     /**
 813  
      * <p>Divide the value of this fraction by another.</p>
 814  
      *
 815  
      * @param fraction  the fraction to divide by, must not be <code>null</code>
 816  
      * @return a <code>Fraction</code> instance with the resulting values
 817  
      * @throws IllegalArgumentException if the fraction is <code>null</code>
 818  
      * @throws ArithmeticException if the fraction to divide by is zero
 819  
      * @throws ArithmeticException if the resulting numerator or denominator exceeds
 820  
      *  <code>Integer.MAX_VALUE</code>
 821  
      */
 822  
     public Fraction divideBy(final Fraction fraction) {
 823  9
         if (fraction == null) {
 824  1
             throw new IllegalArgumentException("The fraction must not be null");
 825  
         }
 826  8
         if (fraction.numerator == 0) {
 827  1
             throw new ArithmeticException("The fraction to divide by must not be zero");
 828  
         }
 829  7
         return multiplyBy(fraction.invert());
 830  
     }
 831  
 
 832  
     // Basics
 833  
     //-------------------------------------------------------------------
 834  
 
 835  
     /**
 836  
      * <p>Compares this fraction to another object to test if they are equal.</p>.
 837  
      *
 838  
      * <p>To be equal, both values must be equal. Thus 2/4 is not equal to 1/2.</p>
 839  
      *
 840  
      * @param obj the reference object with which to compare
 841  
      * @return <code>true</code> if this object is equal
 842  
      */
 843  
     @Override
 844  
     public boolean equals(final Object obj) {
 845  20
         if (obj == this) {
 846  8
             return true;
 847  
         }
 848  12
         if (obj instanceof Fraction == false) {
 849  3
             return false;
 850  
         }
 851  9
         final Fraction other = (Fraction) obj;
 852  9
         return getNumerator() == other.getNumerator() &&
 853  
                 getDenominator() == other.getDenominator();
 854  
     }
 855  
 
 856  
     /**
 857  
      * <p>Gets a hashCode for the fraction.</p>
 858  
      *
 859  
      * @return a hash code value for this object
 860  
      */
 861  
     @Override
 862  
     public int hashCode() {
 863  6
         if (hashCode == 0) {
 864  
             // hashcode update should be atomic.
 865  4
             hashCode = 37 * (37 * 17 + getNumerator()) + getDenominator();
 866  
         }
 867  6
         return hashCode;
 868  
     }
 869  
 
 870  
     /**
 871  
      * <p>Compares this object to another based on size.</p>
 872  
      *
 873  
      * <p>Note: this class has a natural ordering that is inconsistent
 874  
      * with equals, because, for example, equals treats 1/2 and 2/4 as
 875  
      * different, whereas compareTo treats them as equal.
 876  
      *
 877  
      * @param other  the object to compare to
 878  
      * @return -1 if this is less, 0 if equal, +1 if greater
 879  
      * @throws ClassCastException if the object is not a <code>Fraction</code>
 880  
      * @throws NullPointerException if the object is <code>null</code>
 881  
      */
 882  
     @Override
 883  
     public int compareTo(final Fraction other) {
 884  14
         if (this==other) {
 885  7
             return 0;
 886  
         }
 887  7
         if (numerator == other.numerator && denominator == other.denominator) {
 888  1
             return 0;
 889  
         }
 890  
 
 891  
         // otherwise see which is less
 892  5
         final long first = (long) numerator * (long) other.denominator;
 893  5
         final long second = (long) other.numerator * (long) denominator;
 894  5
         if (first == second) {
 895  2
             return 0;
 896  3
         } else if (first < second) {
 897  1
             return -1;
 898  
         } else {
 899  2
             return 1;
 900  
         }
 901  
     }
 902  
 
 903  
     /**
 904  
      * <p>Gets the fraction as a <code>String</code>.</p>
 905  
      *
 906  
      * <p>The format used is '<i>numerator</i>/<i>denominator</i>' always.
 907  
      *
 908  
      * @return a <code>String</code> form of the fraction
 909  
      */
 910  
     @Override
 911  
     public String toString() {
 912  8
         if (toString == null) {
 913  7
             toString = new StringBuilder(32)
 914  
                 .append(getNumerator())
 915  
                 .append('/')
 916  
                 .append(getDenominator()).toString();
 917  
         }
 918  8
         return toString;
 919  
     }
 920  
 
 921  
     /**
 922  
      * <p>Gets the fraction as a proper <code>String</code> in the format X Y/Z.</p>
 923  
      *
 924  
      * <p>The format used in '<i>wholeNumber</i> <i>numerator</i>/<i>denominator</i>'.
 925  
      * If the whole number is zero it will be omitted. If the numerator is zero,
 926  
      * only the whole number is returned.</p>
 927  
      *
 928  
      * @return a <code>String</code> form of the fraction
 929  
      */
 930  
     public String toProperString() {
 931  11
         if (toProperString == null) {
 932  10
             if (numerator == 0) {
 933  1
                 toProperString = "0";
 934  9
             } else if (numerator == denominator) {
 935  1
                 toProperString = "1";
 936  8
             } else if (numerator == -1 * denominator) {
 937  1
                 toProperString = "-1";
 938  7
             } else if ((numerator>0?-numerator:numerator) < -denominator) {
 939  
                 // note that we do the magnitude comparison test above with
 940  
                 // NEGATIVE (not positive) numbers, since negative numbers
 941  
                 // have a larger range.  otherwise numerator==Integer.MIN_VALUE
 942  
                 // is handled incorrectly.
 943  6
                 final int properNumerator = getProperNumerator();
 944  6
                 if (properNumerator == 0) {
 945  2
                     toProperString = Integer.toString(getProperWhole());
 946  
                 } else {
 947  4
                     toProperString = new StringBuilder(32)
 948  
                         .append(getProperWhole()).append(' ')
 949  
                         .append(properNumerator).append('/')
 950  
                         .append(getDenominator()).toString();
 951  
                 }
 952  6
             } else {
 953  1
                 toProperString = new StringBuilder(32)
 954  
                     .append(getNumerator()).append('/')
 955  
                     .append(getDenominator()).toString();
 956  
             }
 957  
         }
 958  11
         return toProperString;
 959  
     }
 960  
 }