CODEWITHSUNDEEP
javaalgorithm
James
James

Reputation: 469

Why is my program giving an incorrect output in certain cases?

I have made an implementation of the Euclidean Algorithm in Java to find the Greatest Common Divisor (GCD) of two given numbers.

For the most part, my program works fine, I have tested it with a few random sets of numbers, although, I have found in one case (that I know of) that it's giving an incorrect output, which is for the following combination of numbers:

Enter integer a: 8965 Enter integer b: 55

The output of the program should be 55, although this is not the case. The out given is as follows:

gcd = 1 Execution time: 0.005747ms.

I'm not sure why this particular combination of numbers is causing a problem, as it works fine for other numbers, for example, here is the results for a different set of numbers:

Enter integer a: 15000

Enter integer b: 5325

gcd = 75

Execution time: 0.007389ms.

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) {
        if ( (a == 0) || (b == 0)) {
            return 0;
        }
        if (b > a) {
            int temp = a;
            a = b;
            b = temp;
        }
        int gcd = 1;
        while(gcd != 0) {
            if( (a % b) == 0) {
                break;
            }
            gcd = a % b;
            a  = b;
            b = gcd;
        }
        return gcd;
    }
}

Upvotes: 4

Views: 128

Answers (3)

rgettman
rgettman

Reputation: 178263

Whenever one of your numbers a, b is a multiple of the other, then your if condition will cause a break and 1 will be returned, which is incorrect. But the rest of the algorithm is incorrect also.

According to the pseudocode for the Euclidean Algorithm:

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

You need to check if b is not 0, not the gcd. You'll need to modify your code to match this algorithm; your code is not currently matching this algorithm.

Upvotes: 4

HopefullyHelpful
HopefullyHelpful

Reputation: 1799

It's easy 55 divides 8965 that means you programm breaks in the first line and returns your initial value which is 1.

Instead something like this could help.

int gcd = 1;
if( (a % b) == 0) {
   return b;
}
while(gcd != 0) {
    if( (a % b) == 0) {
        break;
    }
    gcd = a % b;
    a  = b;
    b = gcd;
}

Upvotes: 1

Pham Trung
Pham Trung

Reputation: 11284

Because of the if condition inside this while loop

int gcd = 1;
while(gcd != 0) {
    if( (a % b) == 0) {
        break;
    }
    gcd = a % b;
    a  = b;
    b = gcd;
}

So, in case a % b = 0 at the beginning -> result is always equaled to 1.

You need to handle that case separately.

int gcd = b;
while(a % b != 0){
   gcd = a % b;
   a = b;
   b = gcd;
}

Upvotes: 3

Related Questions