home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / modula2 / library / modula1 / gcdlcm.mod < prev    next >
Text File  |  1987-06-11  |  1KB  |  32 lines
  1. (* Compute the greatest common divisor (gcd) and the lowest common
  2.    multiple (lcm) of two natural numbers by using addition and
  3.    subtraction only.  Note that gcd(m,n) * lcm(m,n) = m*n.  Repeat
  4.    reading pairs of integers until you encounter a 0.  For each
  5.    pair, print the arguments, the gcd and the lcm.
  6.    Indicate the loop invariant.*)
  7.  
  8. MODULE gcdlcm;
  9. FROM InOut IMPORT ReadCard, WriteLn, WriteString, WriteCard;
  10.  
  11. VAR x,y,u,v: CARDINAL;
  12.  
  13. BEGIN
  14.   WriteString('x = '); ReadCard(x); WriteLn;
  15.   WHILE x # 0 DO
  16.     WriteString('y = '); ReadCard(y);
  17.     u := x; v := y;
  18.     WHILE x # y DO
  19.       (*gcd(x,y) = gcd(x0,y0), x*v + y*u = 2*x0*y0*)
  20.       IF x > y THEN
  21.         x := x-y;
  22.         u := u+v;
  23.       ELSE
  24.         y := y-x;
  25.         v := v+u;
  26.       END
  27.     END;
  28.     WriteCard(x,6); WriteCard((u+v) DIV 2,6); WriteLn;
  29.     WriteString('x = '); ReadCard(x); WriteLn;
  30.   END;
  31. END gcdlcm.
  32.