Java Programming Tutorials

Java programming tutorials with many code examples!

GCD in Java using Euclidean Algorithm

In this post we show how to implement GCD in Java using Euclidean Algorithm. GCD is known as Greatest Common Divisor/Factor/Measure, Highest Common Divisor/Factor.

Greatest Common Divisor of integers is the largest positive integer that divides the numbers without a reminder. There are many ways to calculate GCD, but in this post we’re going to implement Euclidean Algorithm in a few different ways. The Euclidean algorithm is know for about 2300 years and it’s still used today.

How it works

GCD(a, b) works as follows:

  1. If b is 0 then, a is GCD, because any number is divisor of 0 and the greatest divisor of a is |a|.
  2. The result is GCD(b, a mod b), because the greatest common divisor doesn’t change when the larger number is replaced with it’s difference with the smaller number.

Euclidean algorithm – recursively

Recursive version is the simplest implementation of Euclidean algorithm:

public int euclidRecursive(int a, int b) {
    return b == 0 ? Math.abs(a) : euclidRecursive(b, a % b);
}

We use Math.abs(a), because the numbers may be negative and we want to find positive integer.

Euclidean algorithm – iterative version

Here’s the same algorithm, but written iteratively, which is usually preferred for languages without Tail Call Optimization:

public int euclidIterative(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return Math.abs(a);
}

GCD of many numbers

To calculate GCD(a, b, c, …) we have to recursively calculate Greatest Common Divisor for the first pair, then GCD for the result and the next number, and so on:

public int of(int a, int b, int... ints) {
    int gcd = euclidIterative(a, b);
    if (ints != null) {
        for (int i : ints) {
            gcd = euclidIterative(gcd, i);
        }
    }
    return Math.abs(gcd);
}

Unit tests

Here are sample JUnit tests to show that it all works:

package com.farenda.tutorials.algorithms.numbers;

import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class GCDTest {

    private GCD gcd = new GCD();

    @Test
    public void gcdOfZeroAndNumberIsNumber() {
        assertEquals(42, gcd.euclidIterative(0, 42));
        assertEquals(42, gcd.euclidRecursive(0, 42));
    }

    @Test
    public void shouldCalculateGCDofTwoPositiveNumbers() {
        assertEquals(120, gcd.euclidIterative(1080, 1920));
        assertEquals(120, gcd.euclidRecursive(1080, 1920));

        assertEquals(120, gcd.euclidIterative(1920, 1080));
        assertEquals(120, gcd.euclidRecursive(1920, 1080));
    }

    @Test
    public void shouldCalculateForNegativeNumber() {
        assertEquals(3, gcd.euclidIterative(21, -9));
        assertEquals(3, gcd.euclidRecursive(21, -9));

        assertEquals(3, gcd.euclidIterative(-21, 9));
        assertEquals(3, gcd.euclidRecursive(-21, 9));

        assertEquals(3, gcd.euclidIterative(-21, -9));
        assertEquals(3, gcd.euclidRecursive(-21, -9));
    }

    @Test
    public void shouldCalculateForMultipleNumbers() {
        assertEquals(3, gcd.of(12, 6, -21, 33));
    }
}

References:

Share with the World!