JavaWorld

Wednesday, June 18, 2014

Alogrithms - I Euclide's greater common divisor

In Algorithms series of articles we will go from zero ground level to a high level expert in algorithms. We want to broadly share such a knowledge with anybody who desires to learn and to grow.

Let's start with something very basic: Euclide's algorithms.

Euclides algorithms is based on the following statements about the greater common divisor of two numbers

p and q (p >= q)

if q equals zero then p divides p and p divides q therefore p is the G.C.D

otherwise the GDC is the same as the GCD of q and the remainder of p/q

Such an algorithm is clearly suited for a reflective implementation. Therefore we have chosen to implement it recursively in java. Here is an example of implementation

package org.hypernovae.hyperutils.algotils;

public final class Euclide {

private Euclide() {

}

public static int gcd(int p, int q) {

if (q == 0) {
return p;
}

int r = p%q;
return gcd(q,r);

}


}

0 Comments:

Post a Comment

<< Home