Euclidean Algorithm

Euclidean Algorithm

The Euclidean algorithm is an algorithm to determine the greatest common divisor (GCD). The most important characteristic is that it does not require require factoring the two integers (a,b).

Traditional version (best to understand the algorithm)

The real traditional version used only subtraction operations though. So I would call this algorithm,
the semi-traditional one :)

int gcd(int a, int b){
    int c;
    while(b > 0){
        int c = a % b;
        a = b;
        b = c;
    }
    return a;
}

Recursion

int gcd(int a, int b){
    if(b == 0)
        return a;
    return gcd(b, a % b);
}

Non Recursion (faster)

Divsion by zero is handled too with this algorithm. When b == 0,
the loop will never be entered and thus a is returned.

int gcd(int a, int b){
    while(a && b){
        a = a % b;
        if(a)
            b = b % a;
    }
    return a + b;
}

Optimized version

inline int gcd(int a, int b)  __attribute__((always_inline));
 
// Optimized Euclidean algorithm to calculate gcd. 
// If result == 1, the two numbers are co-primes 
inline int gcd(register int aco, register int bco) {
    if(bco && !((aco % 2 == 0 ) && (bco % 2 == 0))) {
        while((aco %= bco) && (bco %= aco)  ) { }
    }
    return aco + bco;
}

More info: http://en.wikipedia.org/wiki/Euclidean_algorithm

Excellent demonstration of the Euclidean algorithm (done by Chun-Hung Hsiao)

http://ntucsie-c2007.googlegroups.com/web/euclidean.ppt?gda=euPa4D4AAAAtQpGR7NTUjkiC4vYIGWnAymlQ5j0rw9LSF0NaLv98KGG1qiJ7UbTIup-M2XPURDQYvV3fRIqFKSm57izjLQ_T

The file is also attached to this wiki topic.

Faster alternatives

Attention: This has to be verified! Some simple tests showed that the optimized euclidean algorithm was a lot faster than binary gcd for numbers within a certain range.

Binary GCD
http://en.wikipedia.org/wiki/Binary_GCD_algorithm
Lehmer's Algorithm
http://www.imsc.res.in/~kapil/crypto/notes/node11.html

Performance measurement

b96123@linux1:~/workspace/homework/a3_problem2_coprime> more input3
2 3 4
9 20 351
15 13 99
45 90 1112043
3 3 3
b96123@linux1:~/w
 
Simple Euclidean Algorithm
--------------------------
b96123@linux1:~/workspace/homework/a3_problem2_coprime> time ./seuclid.out < input3
1
221
47
593042
0
0.076u 0.000s 0:00.07 100.0%    0+0k 0+0io 0pf+0w
b96123@linux1:~/workspace/homework/a3_problem2_coprime>
 
Binary GCD
----------
b96123@linux1:~/workspace/homework/a3_problem2_coprime> time ./binarygcd.out < input3
1
221
47
593042
0
0.244u 0.004s 0:00.25 96.0%     0+0k 0+0io 0pf+0w
b96123@linux1:~/workspace/homework/a3_problem2_coprime>
 
GCD Extended
------------
b96123@linux1:~/workspace/homework/a3_problem2_coprime> time ./gcdext.out < input3
1
221
47
593042
0
0.276u 0.000s 0:00.27 100.0%    0+0k 0+0io 0pf+0w
b96123@linux1:~/workspace/homework/a3_problem2_coprime>

See also Computational complexity of mathematical operations

http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

Open Questions

Which GCD algorithm for which type of numbers (1 - 1mio, 1 mrd - 100 mrd, …)?

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License