home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / C / C80TCOG.ZIP / GCD.C < prev    next >
Encoding:
C/C++ Source or Header  |  1988-08-08  |  1.6 KB  |  66 lines
  1. /* gcd - greatest common divisor of two integers                */
  2. /*                                                      1982/10/17 12:11
  3.         submitted by    William G. Hutchison, Jr.
  4.                         P.O. Box 278
  5.                         Exton, PA 19341-0278
  6.                         U.S.A.
  7.  
  8.                         CompuServe 70665,1307
  9.  
  10.  */
  11.  
  12. #ifdef UNIX
  13. unsigned
  14. #endif
  15. gcd(x,y)int x,y;
  16. {
  17.         return(gcdu(abs(x),abs(y)));
  18. } /* end gcd */
  19.  
  20. #ifdef UNIX
  21. unsigned
  22. #endif
  23. gcdu(u, v)unsigned u, v;
  24. {
  25.         register unsigned k, x, y; 
  26.         x= u, y= v;
  27.         if(x==0||y==0)return(1);
  28.         for(k= 0; (((x|y) & 1) == 0); k++) {
  29.                 x>>=1; 
  30.                 y>>=1;
  31.         }
  32.         /* gcdu(u, v) = (2^k) * gcdu(x,y) */
  33.         do{ /* odd(x) | odd(y) */
  34.  
  35.                 while((x&1) == 0) x>>=1;
  36.                 while((y&1) == 0) y>>=1;
  37.                 /* odd(x) & odd(y) */
  38.                 if (x > y) x-= y; 
  39.                 else y-= x;
  40.         }    while (x>0 && y>0);
  41.         return((x==0? y:x) << k);
  42. } /* end gcdu */
  43.  
  44. /* Alagic, Suad & Arbib, Michael A. "The Design of Well Structured
  45. and Correct Programs" Springer-Verlag, New York 1978, p. 225.   */
  46.  
  47. #ifdef MAINLY
  48. #else
  49. #include "c80def.h"
  50. #include "printf.c"
  51.  
  52. main() {
  53.         int p, q;
  54.         p= 2*3*5*7*17; 
  55.         q= 11*13*17;
  56.         printf("gcd(%d,%d)=%d\n", p, q, gcd(p, q));
  57.         for(p= 0; p < 21; p++) for(q=0; q < 21; q++)
  58.                 printf("gcd(%3d,%3d)=%d\n", p, q, gcd(p, q));
  59. } /* end main */
  60.  
  61. abs(x)int x;
  62. {
  63.         return(x>=0? x:-x);
  64. } /* end abs */
  65. #endif
  66.