(* Compute the greatest common divisor (gcd) and the lowest common
  multiple (lcm) of two natural numbers by using addition and
  subtraction only.  Note that gcd(m,n) * lcm(m,n) = m*n.  Repeat
  reading pairs of integers until you encounter a 0.  For each
  pair, print the arguments, the gcd and the lcm.
  Indicate the loop invariant.*)

MODULE gcdlcm;
FROM InOut IMPORT ReadCard, WriteLn, WriteString, WriteCard;

VAR x,y,u,v: CARDINAL;

BEGIN
 WriteString('x = '); ReadCard(x); WriteLn;
 WHILE x # 0 DO
   WriteString('y = '); ReadCard(y);
   u := x; v := y;
   WHILE x # y DO
     (*gcd(x,y) = gcd(x0,y0), x*v + y*u = 2*x0*y0*)
     IF x > y THEN
       x := x-y;
       u := u+v;
     ELSE
       y := y-x;
       v := v+u;
     END
   END;
   WriteCard(x,6); WriteCard((u+v) DIV 2,6); WriteLn;
   WriteString('x = '); ReadCard(x); WriteLn;
 END;
END gcdlcm.

You are viewing proxied material from gopher.floodgap.com. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.