# 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)

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, …)?