README.md

Compute Fast GCD Algorithm.

• Reference
  Wikipedia, Euclidean Algorithm - https://en.wikipedia.org/wiki/Euclidean_algorithm
  Wikipedia, Binary GCD Algorithm - https://en.wikipedia.org/wiki/Binary_GCD_algorithm#cite_note-11
  binary gcd 2 - http://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/
  

binary_gcd.c

unsigned int binary_gcd(unsigned int u, unsigned int v)
{
	int shift;

	/* GCD(0,v) == v; GCD(u,0) == u, GCD(0,0) == 0 */
	if (u == 0) return v;
	if (v == 0) return u;

	/* Let shift := lg K, where K is the greatest power of 2
	 *    dividing both u and v. */
	for (shift = 0; !((u | v) & 1); ++shift) {
		u >>= 1;
		v >>= 1;
	}

	while (!(u & 1))
		u >>= 1;

	/* From here on, u is always odd. */
	do {
		/* remove all factors of 2 in v -- they are not common */
		/*   note: v is not zero, so while will terminate */
		while (!(v & 1))  /* Loop X */
			v >>= 1;

		/* Now u and v are both odd. Swap if necessary so u <= v,
		 * then set v = v - u (which is even). For bignums, the
		 * swapping is just pointer movement, and the subtraction
		 * can be done in-place. */
		if (u > v) { unsigned int t = v; v = u; u = t; }  // Swap u and v.
		v = v - u;                       // Here v >= u.
	} while (v);

	/* restore common factors of 2 */
	return u << shift;
}

binary_gcd_2.c

/* 
This (binary gcd algorithm)code Link : http://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/ 
__builtin_ctz : Returns the number of trailing 0-bits in x, 
starting at the least significant bit position. If x is 0, the result is undefined.
(__builtin_ctz info Link : https://gcc.gnu.org/onlinedocs/gcc-4.8.2/gcc/Other-Builtins.html)
*/
unsigned int binary_gcd_2(unsigned int u, unsigned int v)
{
    int shift;
    if (u == 0) return v;
    if (v == 0) return u;
    shift = __builtin_ctz(u | v);
    u >>= __builtin_ctz(u);
    do {
        v >>= __builtin_ctz(v);
        if (u > v) { unsigned int t = v; v = u; u = t; }  
        v = v - u;
    } while (v);
    return u << shift;
}

euclidean_gcd.c

int euclidean_gcd(int a, int b)
{
	int t;
	// a must be bigger than b.
	if (a < b) { t = a; a = b; b = t; }
	
	while (b) { t = b; b = a%b; a = t; }

	return a;
}