Posted By

s1m55r on 06/25/10


Tagged

binary gcd


Versions (?)

Binary GCD


 / Published in: C
 

Compute the GCD of two numbers

  1. typedef unsigned long long uint64;
  2. uint64 gcd(uint64 u, uint64 v)
  3. {
  4. int shift;
  5.  
  6. /* GCD(0,x) := x */
  7. if (u == 0 || v == 0)
  8. return u | v;
  9.  
  10. /* Let shift := lg K, where K is the greatest power of 2
  11.   dividing both u and v. */
  12. for (shift = 0; ((u | v) & 1) == 0; ++shift) {
  13. u >>= 1;
  14. v >>= 1;
  15. }
  16.  
  17. while ((u & 1) == 0)
  18. u >>= 1;
  19.  
  20. /* From here on, u is always odd. */
  21. do {
  22. while ((v & 1) == 0) /* Loop X */
  23. v >>= 1;
  24.  
  25. /* Now u and v are both odd, so diff(u, v) is even.
  26.   Let u = min(u, v), v = diff(u, v)/2. */
  27. if (u < v) {
  28. v -= u;
  29. } else {
  30. uint64 diff = u - v;
  31. u = v;
  32. v = diff;
  33. }
  34. v >>= 1;
  35. } while (v != 0);
  36.  
  37. return u << shift;
  38. }

Report this snippet  

You need to login to post a comment.