# I made a BigFraction class in Java. It's a bit slow

Thanks for looking it over. I'm still pretty new to programming. I thought this would be a good exercise in addition to making the Project Euler fraction problems easier

import java.math.BigInteger;

final class BigFraction extends Number{

private BigInteger numerator;
private BigInteger denominator;
public final static BigFraction ZERO = new BigFraction(BigInteger.ZERO);

public BigFraction(String numerator, String denominator, boolean reduce){
this(new BigInteger(numerator), new BigInteger(denominator));
if(reduce)
this.reduce();
}
public BigFraction(long numerator, long denominator){
this(BigInteger.valueOf(numerator), BigInteger.valueOf(denominator));
}
public BigFraction(String numerator, String denominator){
this(new BigInteger(numerator), new BigInteger(denominator));
}
public BigFraction(BigInteger numerator, BigInteger denominator){
if(denominator.signum() == 0)
throw new IllegalArgumentException("Denominator can't be zero");
if(numerator.signum() == 0){
denominator = BigInteger.ONE;
}

if(denominator.signum() == -1){
numerator = numerator.multiply( BigInteger.valueOf(-1 ));
denominator = denominator.multiply( BigInteger.valueOf(-1 ));
}

this.numerator = numerator;
this.denominator= denominator;

}
public void reduce(){
if( ! this.numerator.equals(BigInteger.ZERO) ){
BigInteger GCF = (GCF(this.numerator, this.denominator)).abs();
this.numerator = this.numerator.divide(GCF);
this.denominator = this.denominator.divide(GCF);
}
}
public BigFraction(BigInteger numerator){
this.numerator = numerator;
this.denominator = BigInteger.ONE;
}
public static BigFraction valueOf(long numerator, long denominator){
return new BigFraction(BigInteger.valueOf(numerator), BigInteger.valueOf(denominator));
}
public static BigFraction valueOf(long numerator){
return new BigFraction(BigInteger.valueOf(numerator));
}
public BigFraction multiply(BigFraction frac){
BigInteger newNumerator = this.getNumerator().multiply( frac.getNumerator() );
BigInteger newDenominator = this.getDenominator().multiply( frac.getDenominator() );
return new BigFraction(newNumerator, newDenominator);
}
public BigFraction divide(BigFraction frac){
return this.multiply(new BigFraction(frac.getDenominator(), frac.getNumerator()) );
}
public BigFraction add(BigFraction frac){
BigInteger LCM = LCM(frac);
BigInteger fracNum = ( LCM.divide( frac.getDenominator() )).multiply( frac.getNumerator() );
BigInteger thisNum = ( LCM.divide( this.getDenominator() )).multiply( this.getNumerator() );
return new BigFraction( thisNum.add(fracNum), LCM );
}
public BigFraction subtract(BigFraction frac){
BigInteger LCM = LCM(frac);
BigInteger fracNum = (LCM.divide( frac.getDenominator() )).multiply( frac.getNumerator() );
BigInteger thisNum = (LCM.divide( this.getDenominator() )).multiply( this.getNumerator() );
return new BigFraction(thisNum.subtract( fracNum), LCM);
}
public String toString(){
return this.getNumerator()+"/"+this.getDenominator();
}
public BigInteger getNumerator(){
return this.numerator;
}
public BigInteger getDenominator(){
return this.denominator;
}
@Override
public int intValue() {
return (int) this.doubleValue();
}
@Override
public long longValue() {
return (long) this.doubleValue();
}
@Override
public float floatValue() {
return (float) this.doubleValue();
}
@Override
public double doubleValue() {
return (this.numerator).doubleValue() / (this.denominator).doubleValue();
}
public boolean equals(BigFraction frac){
return this.compareTo(frac) == 0;
}
public int compareTo(BigFraction frac){
BigInteger t = this.getNumerator().multiply( frac.getDenominator() );
BigInteger f = frac.getNumerator().multiply( this.getDenominator() );

int result = 0;

if(t.max(f).equals(t))
return 1;
if(f.max(t).equals(f))
return -1;
return result;
}
public BigInteger LCM(BigFraction frac){
return (frac.getDenominator().multiply( this.getDenominator()).abs()).divide( GCF(frac.getDenominator(), this.getDenominator() ) ) ;
}
public boolean isReduced(){
BigInteger tempDenominator = numerator.min(denominator);
BigInteger tempNumerator = numerator.max(denominator);

BigInteger remainder = tempDenominator.mod( tempNumerator );
while(! remainder.equals(BigInteger.ZERO)){
remainder = tempDenominator.mod( tempNumerator );
tempDenominator = tempNumerator;
tempNumerator = remainder;
}
return tempDenominator.equals(BigInteger.ONE);
}
private BigInteger GCF(BigInteger numerator, BigInteger denominator){

BigInteger tempDenominator = numerator.min(denominator);
BigInteger tempNumerator = numerator.max(denominator);
numerator = tempNumerator;
denominator = tempDenominator;

BigInteger remainder = denominator.mod( numerator );
while(! remainder.equals(BigInteger.ZERO)){
remainder = denominator.mod( numerator );
denominator = numerator;
numerator = remainder;
}

return denominator;
}
}

• Can you specify what is slow? All operations? – mheinzerling Apr 17 '13 at 7:10

You should use BigInteger.gcd() instead of GCF(), also in isReduced(). Don't use compareTo in equals: If your fractions are always in reduced form, you can just compare numerators and denominators. In compareTo, you could test some special cases to avoid multiplication, e.g. a/b > c/d if a > c and b <= d (for a,b,c,d > 0).

I think for multiplication a/b * c/d, it could be faster to reduce a and d, as well as b and c, instead of doing the reduction after the multiplication.

There is a BigFraction class in Apache Commons, maybe you can get some inspiration there...

BTW, method and variable names should be lower-case.

[Update]

I think you should always reduce fractions. This allows you to use shortcuts (e.g. in equals and compareTo), and also faster calculations. If fractions are always reduced, you can compare numerators and denominators in equals (instead of calling compareTo). Further, for multiplication you can reduce before you multiply:

public BigFraction multiply(BigFraction frac){
BigInteger gcd1 = this.getNumerator().gcd(frac.getDenominator());
BigInteger num1 = this.getNumerator().divide(gcd1);
BigInteger den1 = frac.getDenominator().divide(gcd1);

BigInteger gcd2 = frac.getNumerator().gcd(this.getDenominator());
BigInteger num2 = frac.getNumerator().divide(gcd2);
BigInteger den2 = this.getDenominator().divide(gcd2);

BigInteger newNumerator = num1.multiply(num2);
BigInteger newDenominator = den1.multiply(den2);
return new BigFraction(newNumerator, newDenominator); //already reduced
}


I'm not sure this is faster, but it's worth a try.

Concerning lower-case variable and method names I thought about things like BigInteger LCM = LCM(frac);.

• Thank you for your input. I had no idea about the BigInteger.gcd(). Weird thing to miss, I must have looked the BigInteger doc over 100 times. I only caps the final variables, isn't that according to convention? I'm not sure I understand the second half of your comments, would you mind clarifying? Also, it isn't always in reduced form. The reduce() function has to be called in order to reduce it. – Josh Apr 17 '13 at 8:42
• @Josh, I would suggest (and it appears that Landei may have suggested) that you always reduce, at the end of every method. – raptortech97 Apr 22 '13 at 22:47
• @Josh According to the convention, only constants are all uppercase, which means only static final fields which never change their content (primitives and Strings never do, a byte[] may or may not change). I gave it a try, too (and the reduction gets always done). I haven't yet benchmark it. – maaartinus Dec 14 '14 at 7:47