{VERSION 5 0 "SGI MIPS UNIX" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 3 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }1 0 0 0 8 4 0 0 0 0 0 0 -1 0 } {PSTYLE "" 2 6 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 2 0 0 0 } 0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Warning" 2 7 1 {CSTYLE "" -1 -1 "" 0 1 0 0 255 1 0 0 0 0 0 0 1 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Diagnostic" 7 9 1 {CSTYLE "" -1 -1 "" 0 1 64 128 64 1 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 } 3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 3 "" 0 "" {TEXT -1 56 "Maple Summer Workshop '04: Programming in Maple Tutorial" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 59 "Examples of Euclid's algorithm: Michael Monagan, June 2004." }{TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 94 "Here is a first iterati ve procedure for computing the greatest common divisor of two integers " }{XPPEDIT 18 0 "a;" "6#%\"aG" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "b ;" "6#%\"bG" }{TEXT -1 2 " ." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 156 "GCD := proc(a::integer,b::integer) local c,d,r;\n c := abs(a );\n d := abs(b);\n while d <> 0 do r := irem(c,d); c := d; d := r; od;\n return c;\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "GCD(24,10);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "trace(GCD);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%$GCDG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "GC D(10,24);" }}{PARA 9 "" 1 "" {TEXT -1 29 "\{--> enter GCD, args = 10, \+ 24" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"cG\"#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"dG\"#C" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG\"# 5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"cG\"#C" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"dG\"#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG\" \"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"cG\"#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"dG\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG\" \"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"cG\"\"%" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%\"dG\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG \"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"cG\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"dG\"\"!" }}{PARA 9 "" 1 "" {TEXT -1 36 "<-- exit GCD (now at top level) = 2\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"# " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 59 "This version uses multiple as signments to improve the code." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 134 "GCD := proc(a::integer,b::integer) local c,d,r;\n (c,d) := abs(a),abs(b);\n while d <> 0 do (c,d) := (d,irem(c,d)) od;\n c ;\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "GCD(10,24);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "trace(GCD);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%$GCDG " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "GCD(10,24);" }}{PARA 9 "" 1 "" {TEXT -1 29 "\{--> enter GCD, args = 10, 24" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>6$%\"cG%\"dG6$\"#5\"#C" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>6$%\"cG%\"dG6$\"#C\"#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>6$% \"cG%\"dG6$\"#5\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>6$%\"cG%\"dG6 $\"\"%\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>6$%\"cG%\"dG6$\"\"#\" \"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}{PARA 9 "" 1 "" {TEXT -1 36 "<-- exit GCD (now at top level) = 2\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 173 "This ver sion is a recursive one. It is not as space efficient because it has \+ to remember all the intermediate integers (they are stored (not visibl e) on the runtime stack)." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 180 "GCD := proc(a::integer,b::integer)\n if a<0 then GCD(abs(a),b) \n elif b<0 then GCD(a,abs(b))\n elif b=0 then a\n elif a " 0 "" {MPLTEXT 1 0 11 "GCD(24,10);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "tra ce(GCD);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%$GCDG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "GCD(24,10);" }}{PARA 9 "" 1 "" {TEXT -1 29 "\{--> enter GCD, args = 24, 10" }}{PARA 9 "" 1 "" {TEXT -1 28 "\{--> \+ enter GCD, args = 10, 4" }}{PARA 9 "" 1 "" {TEXT -1 27 "\{--> enter GC D, args = 4, 2" }}{PARA 9 "" 1 "" {TEXT -1 27 "\{--> enter GCD, args = 2, 0" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}{PARA 9 "" 1 "" {TEXT -1 30 "<-- exit GCD (now in GCD) = 2\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}{PARA 9 "" 1 "" {TEXT -1 30 "<-- exit GCD (now in GCD) = 2\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}{PARA 9 "" 1 "" {TEXT -1 30 "<-- exit GCD (now in GCD) = 2\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}{PARA 9 "" 1 "" {TEXT -1 36 "<-- exit GCD (now at top level) = 2\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 81 "Here is a version of the extended \+ Euclidean algorithm in which auxilliary values " }{XPPEDIT 18 0 "s[i]; " "6#&%\"sG6#%\"iG" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "t[i];" "6#&%\" tG6#%\"iG" }{TEXT -1 35 " are computed so that the identity " } {XPPEDIT 18 0 "s[i]*a+t[i]*b = r[i];" "6#/,&*&&%\"sG6#%\"iG\"\"\"%\"aG F*F**&&%\"tG6#F)F*%\"bGF*F*&%\"rG6#F)" }{TEXT -1 13 " holds where " } {XPPEDIT 18 0 "r[i];" "6#&%\"rG6#%\"iG" }{TEXT -1 121 " is the i'th re mainder. The code is using subscripted variables. It outputs all rel ations found as a list of tripples [" }{XPPEDIT 18 0 "s[i],t[i],r[i]; " "6%&%\"sG6#%\"iG&%\"tG6#F&&%\"rG6#F&" }{TEXT -1 3 " ]." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 363 "EEA := proc(a::posint,b::posint) l ocal i,n,s,t,r,q;\n r[0],s[0],t[0] := a,1,0;\n r[1],s[1],t[1] := b,0,1;\n i := 1;\n while r[i] <> 0 do\n q := iquo(r[i-1] ,r[i]);\n r[i+1] := r[i-1]-q*r[i];\n s[i+1] := s[i-1]-q* s[i];\n t[i+1] := t[i-1]-q*t[i];\n i := i+1;\n od;\n \+ n := i;\n [seq( [r[i],s[i],t[i]], i=0..n )];\nend:\n " }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "EEA(24,10);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7'7%\"#C\"\"\"\"\"!7%\"#5F'F&7%\"\"%F&!\"#7%\"\"#F ,\"\"&7%F'F/!#7" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 126 "This version \+ of the extended Euclidean algorithm just prints out the relations as i t finds them, and outputs the final values " }{XPPEDIT 18 0 "s[n],t[n] ,r[n];" "6%&%\"sG6#%\"nG&%\"tG6#F&&%\"rG6#F&" }{TEXT -1 7 " where " } {XPPEDIT 18 0 "r[n] = gcd(a,b);" "6#/&%\"rG6#%\"nG-%$gcdG6$%\"aG%\"bG " }{TEXT -1 2 " ." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 481 "EEA : = proc(a::posint,b::posint) local i,r0,r1,s0,s1,t0,t1,q;\n r0,s0,t0 := a,1,0;\n printf(\"s[0]=%4d t[0]=%4d r[0]=%4d \\n\",s0,t0,r0); \n r1,s1,t1 := b,0,1;\n printf(\"s[1]=%4d t[1]=%4d r[1]=%4d \\ n\",s1,t1,r1);\n i := 1;\n while r1 <> 0 do\n q := iquo(r 0,r1);\n r0,r1 := r1,r0-q*r1;\n s0,s1 := s1,s0-q*s1;\n \+ t0,t1 := t1,t0-q*t1;\n printf(\"r[%d]=%4d s[%d]=%4d t[% d]=%4d \\n\",i,r1,i,s1,i,t1); \n i := i+1;\n od;\n r0,s0 ,t0;\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "EEA(24,10);" }}{PARA 6 "" 1 "" {TEXT -1 32 "s[0]= 1 t[0]= 0 r[0]= 24 " }} {PARA 6 "" 1 "" {TEXT -1 32 "s[1]= 0 t[1]= 1 r[1]= 10 " }} {PARA 6 "" 1 "" {TEXT -1 32 "r[1]= 4 s[1]= 1 t[1]= -2 " }} {PARA 6 "" 1 "" {TEXT -1 32 "r[2]= 2 s[2]= -2 t[2]= 5 " }} {PARA 6 "" 1 "" {TEXT -1 32 "r[3]= 0 s[3]= 5 t[3]= -12 " }} {PARA 11 "" 1 "" {XPPMATH 20 "6%\"\"#!\"#\"\"&" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "0 0 0" 8 }{VIEWOPTS 1 1 0 3 2 1804 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }