Compute Fast GCD Algorithm.
| 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; | |
| } |
| /* | |
| 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; | |
| } |
| 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; | |
| } |