#===== very primitive prototype for the recursive implementation ====== gcdProto:=proc(a,b) if a < b then printf("%15d, %15d\n",a,b); return gcdrec(b,a); end if; if b = 0 then return a; end if; return gcdProto(a-b,b); end proc: #====== simple recursive version =========== gcdrecurse:=proc(a,b) local g,q,r,u,v,h; if b = 0 then return a,1,0; end if; r:=irem(a,b,'q'); g,u,v:=gcdrecurse(b,r); # g=u*b+v*r=u*b+v*(a-q*b) h:=u; u:=v; v:= h-q*v; printf("a=%12d, q=%12d u=%12d, v=%12d, test=%12d\n",a,q,u,v,a*u+b*v); return g,u,v; end proc: #======== standard and simple iterative version ========== gcditerate:=proc(aa::integer,bb::integer) local r,q,a,b,u,um,v,vm,h ; #a=um*aa+vm*bb #b=u *aa+v *bb #r=a-q*b=(um-q*a)*aa+(vm-q*v)*bb; a:=aa; b:= bb; um:=1; vm:=0; u:=0; v:=1; while b>0 do r:=irem(a,b,'q'); #printf("a=%12d, b=%12d q=%12d, r=%12d\n",a,b,q,r); a:=b; b:=r; h:=um; um:=u; u:=h-q*u; h:=vm; vm:=v; v:=h-q*v; printf("a=%12d, q=%12d u=%12d, v=%12d\n",a,q,um,vm); end do; return a,um,vm; end proc: # ======== Lehmer type implementations ========= # ======== First try, standard simple version, base 10 === LehmerAlpha:=proc(aa::integer,bb::integer) local a,b,C,x,xm,xp,al, alm,alp,be,bem,bep,lena, lenb,s,sm,t,tm,r,q,h,running; s:=1; sm:=0; t:=0; tm:=1; a:=aa; b:=bb; while b>0 do printf("a=%d, b=%d\n",a,b); lena := ilog10(a); lenb := ilog10(b); if lena != lenb or a 0) and (xp+al>0) and (xp+be>0) and (x+al>xp+alp) and (x+be>xp+bep) end do; xm := alm*a+bem*b; x := al*a+be*b; a:=xm; b:=x; xm := alm*sm+bem*s; x := al*sm+be*s; sm:=xm; s:=x; xm := alm*tm+bem*t; x := al*tm+be*t; tm := xm; t:=x; end do; end proc: