Thursday, March 10, 2005

The Euclid Algorithm, Greatest Common Divisor (GCD)

Naive GCD

The following algorithm calculates the Greates Common Divisor (GCD), which is the largest integer number able to divide two numbers with no remainder. The algorithm was known since about 500 B.C. (Berman & Paul 2005).

public class Euclid {
    static int gcd(int m, int n) {
        while (m != n) {
            if (m > n) {
                m -= n;
            } else {
                n -= m;
            }
        }

        return m;
    }
    
    public static void main(String[] args) {
        int x = 378;
        int y = 45;
        int z = gcd(x, y);
        System.out.println(z + ", " + x / z + ", " + y / z);
    }
}
Output
9, 42, 5

Euclid GCD

A more efficient algorithm was published by Euclid about 300 B.C. (Berman & Paul 2005).

public class Euclid {
    static int gcd(int m, int n) {
        int r;
        
        while ((r = m % n) != 0) {
            m = n;
            n = r;
        }
        
        return n;
    }
    
    public static void main(String[] args) {
        int x = 378;
        int y = 45;
        int z = gcd(x, y);
        System.out.println(z + ", " + x / z + ", " + y / z);
    }
}
Output
9, 42, 5

No comments: