GENERIC INTERFACE GCD(R (*,RList*));

Arithmetic for Modula-3, see doc for details

Abstract: Generic computation of the greatest common divisor

FROM Arithmetic IMPORT Error;

TYPE T = R.T;

PROCEDURE GCD (u, v: T; ): T;

returns the greatest common divisor for u and v.

PROCEDURE LCM (u, v: T; ): T;

returns the least common multiple for u and v.

PROCEDURE BezoutGCD
  (u, v: T; VAR (*OUT*) c: ARRAY [0 .. 1], [0 .. 1] OF T; ): T;

returns GCD(u,v) and 'small' factors in the matrix c such that c[0,0]*u+c[0,1]*v=GCD(u,v) c[1,0]*u+c[1,1]*v=0.

PROCEDURE Bezout
  (u, v, w: T; VAR (*OUT*) c: ARRAY [0 .. 1], [0 .. 1] OF T; )
  RAISES {Error};

returns 'small' factors in the matrix c such that c[0,0]*u+c[0,1]*v=w c[1,0]*u+c[1,1]*v=0 . w must be divisible by GCD(u,v), otherwise Err.indivisible is raised.

TYPE
  MAC = REF RECORD
              next  : MAC;
              factor: T;
            END;

PROCEDURE MACDecompose (u, v: T; VAR (*OUT*) mac: MAC; ): T;

returns the greatest common divisor of u and v and writes a list of Multiply&Accumulate operations to 'mac' Start with x := GCD(u,v); y := Zero; Iterate y := y + x*mac; Swap(x,y); mac := mac.tail; at the end u=x and v=y

END GCD.