private Fraction addSub ( final Fraction fraction , final boolean isAdd ) { Validate . isTrue ( fraction != null , "The fraction must not be null" ) ; // zero is identity for addition. if ( numerator == 0 ) { return isAdd ? fraction : fraction . negate ( ) ; } if ( fraction . numerator == 0 ) { return this ; } // if denominators are randomly distributed, d1 will be 1 about 61% // of the time. final int d1 = greatestCommonDivisor ( denominator , fraction . denominator ) ; if ( d1 == 1 ) { // result is ( (u*v' +/- u'v) / u'v') final int uvp = mulAndCheck ( numerator , fraction . denominator ) ; final int upv = mulAndCheck ( fraction . numerator , denominator ) ; return new Fraction ( isAdd ? addAndCheck ( uvp , upv ) : subAndCheck ( uvp , upv ) , mulPosAndCheck ( denominator , fraction . denominator ) ) ; } // the quantity 't' requires 65 bits of precision; see knuth 4.5.1 // exercise 7. we're going to use a BigInteger. // t = u(v'/d1) +/- v(u'/d1) final BigInteger uvp = BigInteger . valueOf ( numerator ) . multiply ( BigInteger . valueOf ( fraction . denominator / d1 ) ) ; final BigInteger upv = BigInteger . valueOf ( fraction . numerator ) . multiply ( BigInteger . valueOf ( denominator / d1 ) ) ; final BigInteger t = isAdd ? uvp . add ( upv ) : uvp . subtract ( upv ) ; // but d2 doesn't need extra precision because // d2 = gcd(t,d1) = gcd(t mod d1, d1) final int tmodd1 = t . mod ( BigInteger . valueOf ( d1 ) ) . intValue ( ) ; final int d2 = tmodd1 == 0 ? d1 : greatestCommonDivisor ( tmodd1 , d1 ) ; // result is (t/d2) / (u'/d1)(v'/d2) final BigInteger w = t . divide ( BigInteger . valueOf ( d2 ) ) ; if ( w . bitLength ( ) > 31 ) { throw new ArithmeticException ( "overflow: numerator too large after multiply" ) ; } return new Fraction ( w . intValue ( ) , mulPosAndCheck ( denominator / d1 , fraction . denominator / d2 ) ) ; }
Implement add and subtract using algorithm described in Knuth 4 . 5 . 1 .