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,

```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;
}
```

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