The greatest common divisor and the common multiple

exercise No. 107

Finding the greatest common divisor of two integer values

Q:

We recall the section called “Example: A class representing fractions”. So far no one demanded cancelling fractions. Yet calling new Fraction(4,8) will create an instance internally being represented by 4 8 rather than by 1 2 .

Cancelling fractions requires implementing e.g. the Euclidean algorithm in order to find the greatest common divisor (GCD) of two non-zero integer values.

Read the above link and implement a class method getGcd(long, long) inside a class Math: 

public static long getGcd(long a, long b) ❶ {
  // Following http://www.math.rutgers.edu/~greenfie/gs2004/euclid.html
  return ??; //TODO
}

With respect to fractions one or both parameters a and b ❶ may be zero or negative. So we do have several special cases to handle:

a == 0 and b == 0

Return 1.

a == 0 and b != 0

Return absolute value of b.

a != 0 and b != 0

Return the gcd of the absolute values of a and b

Based on getGcd(...) implement the least common multiple of two long values:

Tip

Follow the test driven approach: Provide dummy methods and write tests prior to implementation of getGcd(). 

public static long getCommonMultiple(long a, long b) {...}

A:

Implementing getGcd(...): 

public static long getGcd(long a, long b) {

  // Following http://www.math.rutgers.edu/~greenfie/gs2004/euclid.html
  if (a < b) { // Swap the values of a and b
    final long tmp = a;
    a = b;
    b = tmp;
  }
  while (0 != b) {
    final long r = a % b;
    a = b;
    b = r;
  }
  return a;
}

Knowing the the gcd of two values a and b the common multiple may be obtained by a gcd ⁢ b gcd ⁢ gcd = a ⁢ b gcd . Thus we have: 

public static long getLeastCommonMultiple(long a, long b) {
  final long gcd = getGcd(a, b);
  if (1 == gcd) {
    return a * b;
  } else {
    return (a / gcd) * b;
  }
}
Prev  Up  Next
Lotteries revisited  Home  Project dependencies and Maven