Euclid's algorithm GCD finder and fraction simplifier

Question

This program is a practise exercise in using instance methods, and also in recursion which I struggle to get my head around. I want to know how my technique for the recursion could be improved, and if there's anything else which could be made more efficient.

The program creates a Rational object type (a fraction) which has numerator and denominator variables. It runs a method to find the greatest common divisor using Euclid's algorithm, and then prints the simplified form of the fraction.

Any feedback is helpful, but things I'm interested in:

• Is there a more efficient way for me to take the two integers of input (which may both be positive or negative and in any size order) and turn them into two positive integers with the largest first? The if/else section I've used feels excessively big for the simplicity of the task but I couldn't think of another way.
• Is there a way that I could combine the getGcd and reduce methods into a single method? I couldn't work out how to make a method where a subsection of it is recursive but the rest isn't.
• Is there anything that could be improved about my recursive Euclid's algorithm bit? It's pretty simple but I wonder if I missed any tricks to make it extra efficient.

Code:

public class Rational {

public static void main(String[] args) {

    Rational test = new Rational(-462, 1071);
    System.out.println(test.reduce());

}

private int nume;
private int deno;

public Rational(int nume, int deno) {
    this.nume = nume;
    this.deno = deno;
}

public String toString() {
    return this.nume + "/" + this.deno;
}

public Rational reduce() {
    int gcd = this.getGcd();
    return new Rational(this.nume / gcd, this.deno / gcd);
}

public int getGcd() {

    // Set up variables
    int a;
    int b;
    int gcd;
    if (Math.abs(this.nume) > Math.abs(this.deno)) {
        a = Math.abs(this.nume);
        b = Math.abs(this.deno);
    } else {
        a = Math.abs(this.deno);
        b = Math.abs(this.nume);
    }

    // Euclid's algorithm
    if (a%b == 0) {
        gcd =  b;
        return gcd;
    } else {
        gcd = new Rational(b, a%b).getGcd();
        return gcd;
    }

}   

}

Answer 1

First thing: let's make the getGcd static:

public static int gcd(int a, int b){
    if(a % b == 0)
        return b;
    else
        return gcd(b, a % b);
}

This makes things faster if you want to stick with recursion since random instances are not made on every recursive step (otherwise, the while loop tends to win).

In order to handle the signs, I would implement the following (to make later code more readable):

public static boolean isNeg(int a){
    return a < 0;
}

and add a condition to your constructor (this would make this.nume the only possible negative value, beautifying printing and making later code easier):

public Rational(int n, int d){
    if(isNeg(n) == isNeg(d)){
         this.nume = Math.abs(n);
    }else{ 
         this.nume = -1*Math.abs(n);
    }
    this.deno = Math.abs(d);
}

Then, reduce would be the following:

public Rational reduce(){
    int tNume = Math.abs(this.nume);
    //Math.max and Math.min get maximal and minimal values. This is great to
    //reduce the amount of code.
    int gcd = gcd(Math.max(tNume, this.deno), Math.min(tNume, this.deno));
    return new Rational(this.nume / gcd, this.deno / gcd);
}

I would actually probably always reduce for efficient comparison and ease of use (especially for math).

Also: consider throwing an error if this.deno is ever 0 in the constructor.

Answer 2

Euclid's algorithm for computing the greatest common divisor does not require that the two numbers are sorted by absolute value. It works well without that preliminary step:

public int getGcd() {

    int a = Math.abs(this.nume);
    int b = Math.abs(this.deno);

    if (a % b == 0) {
        return b;
    } else {
        return new Rational(b, a % b).getGcd();
    }
}

Note also that the int gcd variable is not needed. But this computes the absolute values in each recursion step. Euclid's algorithm works with signed numbers as well, you can take the absolute value once, as the final step:

public int getGcd() {
    int a = this.nume;
    int b = this.deno;

    if (a % b == 0) {
        return Math.abs(b);
    } else {
        return new Rational(b, a % b).getGcd();
    }
}

But why create an instance of the Rational object in each recursion step? The GCD is a property of two (or possibly more) numbers, and you might want to compute it in other places as well. So make it a static function of the Rational (or some other) class, taking two integers as parameters:

static public int gcd(int a, int b) {
    if (a % b == 0) {
        return Math.abs(b);
    } else {
        return gcd(b, a % b);
    }
}

and call it as

public Rational reduce() {
    int gcd = gcd(this.nume, this.deno);
    return new Rational(this.nume / gcd, this.deno / gcd);
}

There is still a caveat: Your constructor allows the denominator to be zero (and the gcd() function would throw a "division by zero" exception in that case).

You should check the denominator in the constructor and throw an exception for invalid input. You might also want to normalize the fraction and make the denominator positive, in order to avoid a result like 22/-51.

The gcd() function itself can be modified slightly to work if some arguments are zero:

static public int gcd(int a, int b) {
    if (b == 0) {
        return Math.abs(a);
    } else {
        return gcd(b, a % b);
    }
}