Fast GCD : Euclidean Algorithm and Binary GCD Algorithm

GCD Algorithm: Euclidean Algorithm and Binary GCD Algorithm

* Euclidean Algorithm

Wikipedia의 Procedure와 implementation을 이용해서 euclidean_gcd()를 만들었다. 이 함수는 다음과 같은 성질을 이용하여 만들어졌다.

gcd(a, b) = gcd(b, r0)  = gcd(r0, r1) where r0 = a%b and r1 = b % r0. 

아래는 각 알고리즘에 대한 코드입니다.

* Binary GCD
binary gcd는 Wikipedia에서 implementation에 있는 코드를 넣었습니다. procedure은 다음과 같습니다. (Wikipedia - Algorithm)

1. gcd(0, v) = v, because everything divides zero, and v is the largest number that divides v. Similarly, gcd(u, 0) = u. gcd(0, 0) is not typically defined, but it is convenient to set gcd(0, 0) = 0.
2. If u and v are both even, then gcd(u, v) = 2·gcd(u/2, v/2), because 2 is a common divisor.
3. If u is even and v is odd, then gcd(u, v) = gcd(u/2, v), because 2 is not a common divisor. Similarly, if u is odd and v is even, then gcd(u, v) = gcd(u, v/2).
4. If u and v are both odd, and u ≥ v, then gcd(u, v) = gcd((u − v)/2, v). If both are odd and u < v, then gcd(u, v) = gcd((v − u)/2, u). These are combinations of one step of the simple Euclidean algorithm, which uses subtraction at each step, and an application of step 3 above. The division by 2 results in an integer because the difference of two odd numbers is even.^[3]
5. Repeat steps 2–4 until u = v, or (one more step) until u = 0. In either case, the GCD is 2^kv, where k is the number of common factors of 2 found in step 2.

Wikipedia에 설명이 잘 되어있고 code에 주석이 잘 달려있어 특별한 수정을 하지 않은 채로 코드를 작성하였습니다.
그리고 구글링을 하다가 Daniel Lemire's blog(밑의 3번 link 참조)에서 성능이 더 좋다고 하는 코드도 가져왔습니다. 이 블로그에 있는 코드 Algorithm은 Wikipedia의 implementation code와 같으나, 블로그 코드에서 숫자에 있는 2^k factor를 제거하는 부분은 __builtin_ctz() 함수를 사용하였습니다. __builtin_ctz()는 gcc standard C library에 있는 built-in, optimized function이다. 다음은 __builtin_ctz에 대한 설명입니다.(4, 5번 reference link 참조)

— Built-in Function: int __builtin_ctz (unsigned int x)

Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.

Reference

1. Wikipedia, Euclidean Algorithm - https://en.wikipedia.org/wiki/Euclidean_algorithm
2. Wikipedia, Binary GCD Algorithm - https://en.wikipedia.org/wiki/Binary_GCD_algorithm
3. binary gcd 2 - http://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/
4. Examples of built_in functions - http://www.go4expert.com/articles/builtin-gcc-functions-builtinclz-t29238/
5. Document(GCC built_In functions) - https://gcc.gnu.org/onlinedocs/gcc-6.3.0/gcc/Other-Builtins.html#Other-Builtins