##################################################################
# Date: February 9, 1995                                         #
# Dir: teaching/numthy/spring95/maple                            #
# File: euclid_alg                                               #
# Description: This maple proc computes d=gcd(a,b) and finds     #
#              integers x,y such that ax+by=d.                   #
# Note: An example is given at the end.                          #
##################################################################

	euclid:=proc(a,b)
		local r,q,qq,rr,k:
		r:=array(-1..10):
		q:=array(1..10):
	        r[-1]:=a:
		r[0]:=b:
	        qq:=trunc(a/b):
		rr:=a-b*qq:
		k:=0:
	        lprint(qq,rr);
	        while rr>0 do
		   k:=k+1:
	           qq:=trunc(r[k-2]/r[k-1]):
		   rr:=r[k-2]-qq*r[k-1]:
                   r[k]:=rr:
                   q[k]:=qq:
		od:
		lprint(`The gcd is`);
		RETURN(r[k-1]);
	end:
        longeuclid:=proc(a,b)
                      local r,q,qq,rr,k:
		      lprint(`We compute the gcd of `,a,` and `,b,
		              `using the Euclidean algorithm`);	
                      r:=array(-1..10):
                      q:=array(1..10):
                      r[-1]:=a:
                      r[0]:=b:
                      qq:=trunc(a/b):
                      rr:=a-b*qq:
                      k:=0:
                      while rr>0 do
                         k:=k+1:
                         qq:=trunc(r[k-2]/r[k-1]):
                         rr:=r[k-2]-qq*r[k-1]:
                         r[k]:=rr:
                         q[k]:=qq:
			 lprint(r[k-2],`=`,qq,r[k-1],` + `,rr);
                      od:
                      lprint(`Hence, the gcd is` ,r[k-1]);
                      RETURN(r[k-1]);
              end:
      
      	           
        euclidsoln:=proc(a,b)
                      local r,q,qq,rr,k:
		      lprint(`We compute the gcd of `,a,` and `,b,
			     ` using the Euclidean algorithm`);	
                      r:=array(-1..100):
                      q:=array(1..100):
                      r[-1]:=a:
                      r[0]:=b:
                      qq:=trunc(a/b):
                      rr:=a-b*qq:
                      k:=0:
                      while rr>0 do
                         k:=k+1:
                         qq:=trunc(r[k-2]/r[k-1]):
                         rr:=r[k-2]-qq*r[k-1]:
                         r[k]:=rr:
                         q[k]:=qq:
			 lprint(r[k-2],`= (`,qq,`)`,r[k-1],` + `,rr);
                      od:
                      lprint(`Hence, the gcd is` ,r[k-1]);
	              lprint(` `);
                      lprint(`Now we use our computations to find a `);
		      lprint(`solution to the equation`);
                      lprint(a,`(x) + `, b,`(y)= `,r[k-1],`.`);
		      lprint(`We have `);
                      cm:=0:c0:=1:
                      for s from k by (-1) to 2 do
                        s1:=cm:
                        s2:=c0:
                        cm:=s2:
                        c0:=s1-q[s-1]*s2:	
                        if s=k then
                         lprint(r[k-1],`=`,cm,`(`,r[s-3],`) + `,c0,`(`,r[s-2],`)`);
                        else
			 lprint(`       =(`,s1,`)(`,r[s-2],`) + (`,s2,
                               `) ( (`,r[s-3],`)  -  (`,q[s-1],`) (`,r[s-2],`) )`,
                               `=  (`,cm,`) (`,r[s-3],`) +  (`,c0,`) (`,r[s-2],`)`);
                        fi:
                      od:
			lprint(` `);
			lprint(`Hence a solution is `);
			lprint(`x=`,cm,` y=`,c0);
              end:
##################################################################
# > read euclid_alg;
# Warning, `cm` is implicitly declared local
# Warning, `c0` is implicitly declared local
# Warning, `s` is implicitly declared local
# Warning, `s1` is implicitly declared local
# Warning, `s2` is implicitly declared local
# 
# --------------------------------------------------------------------------------
# > euclidsoln(60,37);
# We compute the gcd of  60  and  37 
#  using the Euclidean algorithm
# 60 = ( 1 ) 37  +  23
# 37 = ( 1 ) 23  +  14
# 23 = ( 1 ) 14  +  9
# 14 = ( 1 ) 9  +  5
# 9 = ( 1 ) 5  +  4
# 5 = ( 1 ) 4  +  1
# 4 = ( 4 ) 1  +  0
# Hence, the gcd is 1
#  
# Now we use our computations to find a 
# solution to the equation
# 60 (x) +  37 (y)=  1 .
# We have 
#1 = 1 ( 5 ) +  -1 ( 4 )
#  =( 1 )( 5 ) + ( -1 )( ( 9 )  -  ( 1 )( 5 ) ) =  ( -1 )( 9 ) +  ( 2 )( 5 )
#  =( -1 )( 9 ) + ( 2 )( ( 14 )  -  ( 1 )( 9 ) ) =  ( 2 )( 14 ) +  ( -3 )( 9 )
#  =( 2 )( 14 ) + ( -3 )( ( 23 )  -  ( 1 )( 14 ) ) =  ( -3 )( 23 ) +  ( 5 )( 14 )
#  =( -3 )( 23 ) + ( 5 )( ( 37 )  -  ( 1 )( 23 ) ) =  ( 5 )( 37 ) +  ( -8 )( 23 )
#  =( 5 )( 37 ) + ( -8 )( ( 60 )  -  ( 1 )( 37 ) ) =  ( -8 )( 60 ) +  ( 13 )( 37 )
#  
# Hence a solution is 
# x= -8, y= 13.
# 
# --------------------------------------------------------------------------------
# > 
##################################################################