macro( Rem=`UP/InPlaceRem` );
`UP/EucGcd` := proc(D) local a,b,c,i,da,db,dr,k,l,s,C;

	s := {args[2..nargs]} minus {D[0]};
	if s = {} then RETURN( D[0] ) fi;
	s := sort( [op(s)], D[SmallerEuclideanNorm] );

	C := D[CoefficientRing];
	a := s[1]; s := subsop(1=NULL,s);
	for b in s while a <> D[1] do
		
	    # if RelativelyPrimeHeuristic(C,D,a,b) then RETURN(D[1]) fi;

	    # Euclidean Algorithm coded to run inplace
	    da := D[Degree](a); a := D[ArrayCoeffs](a);
	    db := D[Degree](b); b := D[ArrayCoeffs](b);
	
	    while db > 0 do
		l := C[Inv](b[db]); b[db] := C[1];
		for i from 0 to db-1 do b[i] := C[`*`](l,b[i]) od;
		dr := Rem(C,a,b,da,db,C[1]);
		c := op(b); b := op(a); a := op(c);
		da := db; db := dr
	    od;

	    if db = 0 then RETURN( D[1] ) fi;
	    a := D[Polynom]([seq(a[k], k=0..da)]);

	od;
	D[Normal](a)

end:
save `EucGcd.m`;
quit
