simplifying fractions in Java

Question

My task is to develop a rational class. If 500 and 1000 are my inputs, then (½) must be my output. I have written a program on my own to find it.

Is there another best way to find the solution, or my program is already the best one?

public class Rational {

    public static void main(String[] args){

       int n1 = Integer.parseInt(args[0]);
       int n2 = Integer.parseInt(args[1]); 
       int temp1 = n1;
       int temp2 = n2; 

       while (n1 != n2){
         if(n1 > n2)
            n1 = n1 - n2;
         else
            n2 = n2 - n1;
       }      

      int n3 = temp1 / n1 ;
      int n4 = temp2 / n1 ;

      System.out.print("\n Output :\n");

      System.out.print(n3 + "/" + n4 + "\n\n" );
      System.exit(0);
    }  
}

Answer 1

Interesting question. Here's some executable code that does it with minimal code:

/** @return the greatest common denominator */
public static long gcd(long a, long b) {
    return b == 0 ? a : gcd(b, a % b);
}

public static String asFraction(long a, long b) {
    long gcd = gcd(a, b);
    return (a / gcd) + "/" + (b / gcd);
}

// Some tests
public static void main(String[] args) {
    System.out.println(asFraction(500, 1000)); //  "1/2"
    System.out.println(asFraction(17, 3));     //  "17/3"
    System.out.println(asFraction(462, 1071)); //  "22/51"
}

---

Bonus methods:

/** @return the lowest common multiple */
public static long lcm(long a, long b) {
    return a * b / gcd(a, b);
}

/** @return the greatest common denominator */
public static long gcd(List<? extends Number> numbers) {
    return numbers.stream().map(Number::longValue).reduce((a, b) -> gcd(a, b)).orElseThrow(NoSuchElementException::new);
}

/** @return the lowest common multiple */
public static long lcm(List<? extends Number> numbers) {
    return numbers.stream().map(Number::longValue).reduce((a, b) -> lcm(a, b)).orElseThrow(NoSuchElementException::new);
}

Answer 2

You need the GCD. Either use BigInteger like Nathan mentioned or if you can't, use your own.

public int GCD(int a, int b){
   if (b==0) return a;
   return GCD(b,a%b);
}

Then you can divide each number by the GCD, like you have done above.

This will give you an improper fraction. If you need a mixed fraction then you can get the new numbers. Example if you had 1500 and 500 for inputs you would end up with 3/2 as your answer. Maybe you want 1 1/2. So you just divide 3/2 and get 1 and then get the remainder of 3/2 which is also 1. The denominator will stay the same.

whole = x/y;
numerator x%y;
denominator = y;

In case you don't believe me that this works, you can check out http://en.wikipedia.org/wiki/Euclidean_algorithm

I just happen to like the recursive function because it's clean and simple.

Your algorithm is close, but not exactly correct. Also, you should probably create a new function if you want to find the gcd. Just makes it a little cleaner and easier to read. You can also test that function as well.

Answer 3

For reference, what you implemented is the original subtractive Euclidean Algorithm to calculate the greatest common divisor of two numbers.

A lot faster version is using the remainder from integer division, e.g. % instead of - in your loop:

while (n1 != 0 && n2 != 0){
  if(n1 > n2)
     n1 = n1 % n2;
  else
     n2 = n2 % n1;
}

... and then make sure you will use the one which is not zero.

A more streamlined version would be this:

while(n1 != 0) {
   int old_n1 = n1;
   n1 = n2 % n1;
   n2 = old_n1;
}

and then use n1. Matt's answer shows a recursive version of the same algorithm.

Answer 4

You should make this class something other than a container for static methods. Here is a skeleton

import java.math.BigInteger;
public class BigRational
{
    private BigInteger num;
    private BigInteger denom;
    public BigRational(BigInteger _num, BigInteger _denom)
    {
    //put the negative on top 
    // reduce BigRational using the BigInteger gcd method
    }
    public BigRational()
    {
        this(BigInteger.ZERO, BigInteger.ONE);
    }
    public BigRational add(BigRational that)
    {
    // return this + that;
    }

    .
    .
    .
    //etc
    }
}

Answer 5

I have a similar BigRational class I use. The GcdFunction is makes use of BigInteger's gcd function:

public class GcdFunction implements BinaryFunction {

    @Override
    public BigRational apply(final BigRational left, final BigRational right) {
        if (!(left.isInteger() && right.isInteger())) {
            throw new EvaluationException("GCD can only be applied to integers");
        }
        return new BigRational(left.getNumerator().gcd((right.getNumerator())));

    }

}

BigRational contains a BigInteger numerator and denominator. isInteger() returns true if the simplified ratio's denominator is equal to 1.

Answer 6

Noticed that all answers here do not mention the iterative implementation of the Euclidean algorithm.

  public static long gcdLongIterative(long a, long b) {
    long tmp;
    
    while (0 != b) {
      tmp = b;
      b   = a % b;
      a   = tmp;
    }
    
    return a;
  }  

I implemented the validation test like @Bohemian and both recursive and iterative implementations work the same, however the iterative approach is faster. The benchmarks show small improvement, but it's improvement and overall it feels better to not use the stack so much and depend fully on the Java VM to optimize its implementation depend. Even if the benchmarks would be the same I would still feel better with the iterative as that would be more portable while the recursive was only optimized by my host Java, but might not be so well optimized on other's VMs.

Benchmark results (code is on the bottom of the answer):

(100 000 000 iterations)
gcd recursive:  3113ms
gcd iterative:  3079ms
gcd BigInteger: 13672ms

Signs:

One difference I noticed (besides the performance) is that the signs are handled differently, hand implemented Euclidean algorithm gcdLong and my gcdLongIterative behave the same, but both are different from BigInteger which tends to 'keep' the signs as they are. It seems that in essence the gcd and gcdLongIterative can return a negative number, while BigInteger will return positive only.

gcdLong and gcdLongIterative implementations:
 -4/-2   => 2/1
-10/200  => 1/-20
 10/-200 => 1/-20

BigInteger implementation tends to 'keep' the signs:
 -4/-2   => -2/-1
-10/200  => -1/20
 10/-200 => 1/-20

All results when used for fractions are valid, but it's worth considering post-process normalization if you expect the numbers in a specific 'style'.

For example, if the BigInteger behavior is preferred, then just returning absolute value should be enough, like here:

  public static long gcdLongIterative(long a, long b) {
    long tmp;
    
    while (0 != b) {
      tmp = b;
      b   = a % b;
      a   = tmp;
    }
    
    return Math.abs(a);
  }  

Performance:

Inspired by @Xabster benchmark (from Java: Get Greatest Common Divisor, which method is better?) I extended it to test all 3 implementations, in some cases both recursive and iterative were performing the same, however the iterative is slightly faster in most of the cases.

The benchmark code:

import java.math.BigInteger;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

public class Test {
  
  private static final int BENCHMARK_ITERATIONS = 100000000; 
  

  public static long gcdLong(long a, long b) {
    return b == 0 ? a : gcdLong(b, a % b);
  }

  
  public static long gcdLongIterative(long a, long b) {
    long tmp;
    
    while (0 != b) {
      tmp = b;
      b   = a % b;
      a   = tmp;
    }
    
    return a;
  }  
  
  
  public static long gcdLongBigInteger(long a, long b) {
    return BigInteger.valueOf(a).gcd(BigInteger.valueOf((b))).longValue();
  }

  
  public static String asFractionGcdLong(long a, long b) {
    long gcd = gcdLong(a, b);
    return (a / gcd) + "/" + (b / gcd);
  }

  
  public static String asFractionGcdLongIterative(long a, long b) {
    long gcd = gcdLongIterative(a, b);
    return (a / gcd) + "/" + (b / gcd);
  }
  
  
  public static String asFractionGcdLongBI(long a, long b) {
    long gcd = gcdLongBigInteger(a, b);
    return (a / gcd) + "/" + (b / gcd);
  }
  
  
  public static void test(String actual, String expected) {
    boolean match = expected.equals(actual);
    
    if (match) {
      System.out.println("Actual and expected match=" + expected);      
    } else {
      System.out.println("NO match expected=" + expected + " actual=" + actual);            
    }
  }
  
  
  public static class Values {
    public long   a;
    public long   b;
    public String expected;

    public Values(long a, long b, String expected) {
      this.a = a;
      this.b = b;
      this.expected = expected;
    }
  }
  
  
  public static void validityTest() {
    List<Values> vals = new LinkedList<Values>(Arrays.asList(
        new Values(500, 1000, "1/2"),
        new Values(17,  3,    "17/3"),
        new Values(462, 1071, "22/51"),
        new Values(-4,  -2,   "2/1"),
        new Values(-10, 200,  "1/-20"),
        new Values(10,  -200, "1/-20")
    ));
    
    System.out.println("------  Recursive implementation -------");
    vals.forEach(v -> test(asFractionGcdLong(v.a, v.b), v.expected));
    System.out.println();    
    
    System.out.println("------  Iterative implementation -------");    
    vals.forEach(v -> test(asFractionGcdLongIterative(v.a, v.b), v.expected));
    System.out.println();    

    System.out.println("------  BigInteger implementation -------");    
    vals.forEach(v -> test(asFractionGcdLongBI(v.a, v.b), v.expected));
    System.out.println();    
  }

  
  public static void benchMark() {
    Random r = new Random();
    
    long[] nums = new long[BENCHMARK_ITERATIONS];
    for (int i = 0 ; i < nums.length ; i++) nums[i] = r.nextLong();

    System.out.println("Waming up for benchmark...");
    for (int i = 0 ; i < nums.length-1; i++) gcdLong(i, i + 1);
    for (int i = 0 ; i < nums.length-1; i++) gcdLongIterative(i, i + 1);
    for (int i = 0 ; i < nums.length-1; i++) gcdLongBigInteger(i, i + 1);

    System.out.println("Started benchmark...");
    long s = System.currentTimeMillis();
    for (int i = 0 ; i < nums.length-1; i++) gcdLong(i, i + 1);
    System.out.println("recursive:  " + (System.currentTimeMillis() - s) + "ms");

    s = System.currentTimeMillis();
    for (int i = 0 ; i < nums.length-1; i++) gcdLongIterative(i, i + 1);
    System.out.println("iterative:  " + (System.currentTimeMillis() - s) + "ms");    
    
    s = System.currentTimeMillis();
    for (int i = 0 ; i < nums.length-1; i++) gcdLongBigInteger(i, i + 1);
    System.out.println("BigInteger: " + (System.currentTimeMillis() - s) + "ms");    
  }
  
  
  public static void main(String[] args) {
    validityTest();
    benchMark();
  }
  
}