unsigned int gcd(unsigned int u, unsigned int v)
{
unsigned int shift = 0;
/* 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. */
while (((u | v) & 1) == 0) {
shift++;
u >>= 1;
v >>= 1;
}
while ((u & 1) == 0)
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) == 0)
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 -= u; // Here v >= u.
} while (v != 0);
/* restore common factors of 2 */
return u << shift;
}
I think Binary and Normal GCD hasn't got a very big complexity difference
Both of Their Complexity is Log2(N) ?
(If a have mistake sorry for that)
Yes, both have same complexity but the implementation could improve the code further more. Since this is one of well-known algorithms and useful in many mathematics problems (especially in divisor problems) I think I could learn something more when I try optimize them to use as a template
Normally, it is not needed, especially in ACM problems, but in some special cases of OI problems, algorithms implemented faster by 1.5x or 2x might get you more points when you cant find a better algorithms
Do you prepare to Olympiads? and which?
I'm prepare for other contest. This would not help me much but I am curious to know better algorithms to solve some old problems, and better implementations for some well-known algorithms