CODEWITHSUNDEEP
javaalgorithm
user6179055
user6179055

Reputation:

Euclid's algorithm

In the examples of Euclid's algorithm to calculate gcd(x, y), x is always larger then y. Does this condition matter? What happens if x is smaller then y? Why does this program still returns correct result even if the entered values for x is smaller then y?

import acm.program.*;
/*
GCD Algorithm - greatest common divisor. "Euclid Algorithm approach"

 */
public class EuclidsAlgorithm extends ConsoleProgram {
    public void run(){
        println("This program is calculating the gratest common divisor (GCD) of two numbers.");
        int x = readInt("Enter 1st number: ");
        int y = readInt("Enter 2nd number: ");
        println("GCD(" + x + ", " + y + ") = " + gcd(x, y) );
    }

    private int gcd(int m, int k){
        int r = m % k;
        while (r != 0){
            m = k;
            k = r;
            r = m % k;
        }
        return k;
    }
}

Upvotes: 4

Views: 850

Answers (4)

Pushpinder Singh Grewal
Pushpinder Singh Grewal

Reputation: 101

It returns the correct result because when you divide a smaller number by a greater number ,what you get as the modulus is the smaller number.

So, for example, 10%14 will give you 10. So ,in your logic ,if we take the example of 10 and 14 and pass x as 10 and y as 14, still we will get 2 as the answer which is correct. Though in this code, the while loop will run one more time than if we pass x as 14 and y as 10

Upvotes: 0

Andy Turner
Andy Turner

Reputation: 140504

The order of the inputs doesn't matter to the result.

If m < k, then the initial value of r is simply m; then m receives the value of k, and k receives the value of r, which is m.

As such, the inputs are effectively swapped around on the first iteration of the loop, so that m > k.

Obviously doing this first iteration to swap the inputs takes (slightly) longer than not: if you are able to call the method in such a way that the inputs are already in the m > k order, then you save some work.

Upvotes: 6

nick zoum
nick zoum

Reputation: 7315

The order of the two inputs does not matter since for: r = m%k

if(m < k)
r = m
if(m == k)
r = 0
if(m > k)
r =  an integer number between 0 and k

And r is a number that keeps shrinking and shrinking until a number is found that can divide both numbers or 0 is reached.

Upvotes: 1

hard coder
hard coder

Reputation: 5725

Actually It doesn't matter Here's why

GCD(x,y)
  if (y == 0 ) return x
return GCD(y,x%y)

suppose x = 3, Y = 5

GCD(3,5) = GCD(5,3%5) = GCD(5,3) = GCD(3,2) .....

Upvotes: -1

Related Questions