1
\$\begingroup\$

I have made an implementation of the Euclidean algorithm in Java, following the pseudocode shown below.

As far as my knowledge goes, I can't find a way of making this more efficient.

I have looked into other peoples implementations of this algorithm and there are a few which are slightly shorter, and some that use recursion.

The pseudocode:

function gcd(a, b)
    while b ≠ 0
       t := b
       b := a mod b
       a := t
    return a

My implementation:

import java.util.Scanner;
public class EuclideanAlgorithm {
    public static void main (String [] args) {
        int a, b;
        try(Scanner sc = new Scanner(System.in);) {
            System.out.print("Enter integer a: ");
            a = sc.nextInt();
            System.out.print("Enter integer b: ");
            b = sc.nextInt();
        }
        long start = System.nanoTime();
        int answer = EuclideanAlgorithm(a, b);
        long stop = System.nanoTime();
        System.out.println("gcd = " + answer);
        System.out.println("Execution time: " + ((stop - start) / 1e+6) + "ms.");

    }

    public EuclideanAlgorithm() {}; //Suppress default constructor

    private static int EuclideanAlgorithm(int a, int b) {
        int t;
        while (b != 0) {
            t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
}

Is there a way to make this implementation more efficient, and would it have been more efficient to use recursion?

\$\endgroup\$
2
\$\begingroup\$

I believe this is as efficient as it gets, save for quickly detecting edge cases (a == 0 or a == b), which I think would be negligible anyway.

Recursion wouldn't be more efficient than iterative version. Functional languages can optimize recursion to the point where there's no difference, but I don't think Java excels at that and there's a performance penalty of adding new frames to the stack.

Recursion can make code clearer and more readable sometimes, but that's another story.

As a side note:

public EuclideanAlgorithm() {}; //Suppress default constructor

What's the purpose of this "suppression"?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.