{VERSION 5 0 "IBM INTEL NT" "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 Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "_cstyle3" -1 203 "Times" 0 1 0 0 0 0 0 0 0 2 2 2 0 0 0 1 } {CSTYLE "_cstyle4" -1 207 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 } {CSTYLE "_cstyle5" -1 208 "Courier" 1 12 255 0 0 1 0 1 0 2 1 2 0 0 0 1 }{CSTYLE "_cstyle6" -1 209 "Times" 0 1 0 0 0 0 0 0 0 2 2 2 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 "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 }{PSTYLE "_pstyle4" -1 203 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "_pstyle5" -1 204 1 {CSTYLE "" -1 -1 "Courier" 1 12 255 0 0 1 0 1 0 2 1 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "_pst yle6" -1 205 1 {CSTYLE "" -1 -1 "Times" 0 1 0 0 0 0 0 0 0 2 2 2 0 0 0 1 }0 0 0 -1 -1 -1 2 0 2 0 2 2 -1 1 }{PSTYLE "_pstyle7" -1 206 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 2 2 2 0 0 0 1 }0 0 0 -1 -1 -1 2 0 2 0 2 2 -1 1 }{PSTYLE "_pstyle8" -1 207 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 2 2 2 0 0 0 1 }0 0 0 -1 -1 -1 1 0 1 0 2 2 -1 1 }} {SECT 0 {EXCHG {PARA 203 "" 0 "" {TEXT 207 3 "01." }{TEXT 207 0 "" }}} {EXCHG {PARA 204 "> " 0 "" {MPLTEXT 1 208 20 "karatsuba:=proc(x,y)" } {MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 31 "\nlocal a,b,c,d,n,m,amalc,bmal d;" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 29 "\nn:=nops(convert(x,base, 10));" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 29 "\nm:=nops(convert(y,ba se,10));" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 16 "\nif min(n,m)<=1 " }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 19 "\n then return(x*y)" } {MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 8 "\nend if;" }{MPLTEXT 1 208 0 " " }{MPLTEXT 1 208 13 "\nm:=max(n,m);" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 6 "\nn:=1;" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 28 "\nwhile n \+ " 0 "" {MPLTEXT 1 208 17 "trace(karatsuba):" }{MPLTEXT 1 208 0 "" } {MPLTEXT 1 208 22 "\nkaratsuba(1234,5678):" }{MPLTEXT 1 208 0 "" } {MPLTEXT 1 208 20 "\nuntrace(karatsuba):" }{MPLTEXT 1 208 0 "" }} {PARA 9 "" 1 "" {TEXT -1 39 "\{--> enter karatsuba, args = 1234, 5678 " }}{PARA 9 "" 1 "" {TEXT -1 35 "\{--> enter karatsuba, args = 12, 56 " }}{PARA 9 "" 1 "" {TEXT -1 33 "\{--> enter karatsuba, args = 1, 5" } }{PARA 9 "" 1 "" {TEXT -1 42 "<-- exit karatsuba (now in karatsuba) = \+ 5\}" }}{PARA 9 "" 1 "" {TEXT -1 33 "\{--> enter karatsuba, args = 2, 6 " }}{PARA 9 "" 1 "" {TEXT -1 43 "<-- exit karatsuba (now in karatsuba) = 12\}" }}{PARA 9 "" 1 "" {TEXT -1 34 "\{--> enter karatsuba, args = \+ -1, 1" }}{PARA 9 "" 1 "" {TEXT -1 43 "<-- exit karatsuba (now in karat suba) = -1\}" }}{PARA 9 "" 1 "" {TEXT -1 44 "<-- exit karatsuba (now i n karatsuba) = 672\}" }}{PARA 9 "" 1 "" {TEXT -1 35 "\{--> enter karat suba, args = 34, 78" }}{PARA 9 "" 1 "" {TEXT -1 33 "\{--> enter karats uba, args = 3, 7" }}{PARA 9 "" 1 "" {TEXT -1 43 "<-- exit karatsuba (n ow in karatsuba) = 21\}" }}{PARA 9 "" 1 "" {TEXT -1 33 "\{--> enter ka ratsuba, args = 4, 8" }}{PARA 9 "" 1 "" {TEXT -1 43 "<-- exit karatsub a (now in karatsuba) = 32\}" }}{PARA 9 "" 1 "" {TEXT -1 34 "\{--> ente r karatsuba, args = -1, 1" }}{PARA 9 "" 1 "" {TEXT -1 43 "<-- exit kar atsuba (now in karatsuba) = -1\}" }}{PARA 9 "" 1 "" {TEXT -1 45 "<-- e xit karatsuba (now in karatsuba) = 2652\}" }}{PARA 9 "" 1 "" {TEXT -1 36 "\{--> enter karatsuba, args = -22, 22" }}{PARA 9 "" 1 "" {TEXT -1 34 "\{--> enter karatsuba, args = -3, 2" }}{PARA 9 "" 1 "" {TEXT -1 43 "<-- exit karatsuba (now in karatsuba) = -6\}" }}{PARA 9 "" 1 "" {TEXT -1 33 "\{--> enter karatsuba, args = 8, 2" }}{PARA 9 "" 1 "" {TEXT -1 43 "<-- exit karatsuba (now in karatsuba) = 16\}" }}{PARA 9 " " 1 "" {TEXT -1 35 "\{--> enter karatsuba, args = -11, 0" }}{PARA 9 " " 1 "" {TEXT -1 42 "<-- exit karatsuba (now in karatsuba) = 0\}" }} {PARA 9 "" 1 "" {TEXT -1 45 "<-- exit karatsuba (now in karatsuba) = - 484\}" }}{PARA 9 "" 1 "" {TEXT -1 48 "<-- exit karatsuba (now at top l evel) = 7006652\}" }}}{EXCHG {PARA 203 "" 0 "" {TEXT 207 3 "03." } {TEXT 207 0 "" }}}{EXCHG {PARA 204 "> " 0 "" {MPLTEXT 1 208 20 "karats uba:=proc(x,y)" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 17 "\noption reme mber;" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 31 "\nlocal a,b,c,d,n,m,am alc,bmald;" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 29 "\nn:=nops(convert (x,base,10));" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 29 "\nm:=nops(conv ert(y,base,10));" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 16 "\nif min(n, m)<=1 " }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 19 "\n then return(x*y) " }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 8 "\nend if;" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 13 "\nm:=max(n,m);" }{MPLTEXT 1 208 0 "" } {MPLTEXT 1 208 6 "\nn:=1;" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 28 "\n while n \+ " 0 "" {MPLTEXT 1 208 19 "multiply:=proc(x,y)" }{MPLTEXT 1 208 0 "" } {MPLTEXT 1 208 17 "\noption remember;" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 19 "\nlocal a,b,c,d,n,m;" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 29 "\nn:=nops(convert(x,base,10));" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 29 "\nm:=nops(convert(y,base,10));" }{MPLTEXT 1 208 0 "" } {MPLTEXT 1 208 16 "\nif min(n,m)<=1 " }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 19 "\n then return(x*y)" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 8 "\nend if;" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 13 "\nm:=max(n,m); " }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 6 "\nn:=1;" }{MPLTEXT 1 208 0 " " }{MPLTEXT 1 208 28 "\nwhile n " 0 "" {MPLTEXT 1 208 23 "rnd:=rand(10^49,10^50):" }{MPLTEXT 1 208 0 "" } {MPLTEXT 1 208 10 "\nx:=rnd():" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 10 "\ny:=rnd():" }{MPLTEXT 1 208 0 "" }}}{EXCHG {PARA 203 "" 0 "" {TEXT 207 3 "06." }{TEXT 207 0 "" }}}{EXCHG {PARA 204 "> " 0 "" {MPLTEXT 1 208 14 "start:=time():" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 9 "\nz1:=x*y:" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 14 "\ntime()-s tart;" }{MPLTEXT 1 208 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"\"!F$ " }}}{EXCHG {PARA 203 "" 0 "" {TEXT 207 3 "07." }{TEXT 207 0 "" }}} {EXCHG {PARA 204 "> " 0 "" {MPLTEXT 1 208 14 "start:=time():" } {MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 20 "\nz2:=karatsuba(x,y):" } {MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 14 "\ntime()-start;" }{MPLTEXT 1 208 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"$r#!\"$" }}}{EXCHG {PARA 203 "" 0 "" {TEXT 207 3 "08." }{TEXT 207 0 "" }}}{EXCHG {PARA 204 "> " 0 "" {MPLTEXT 1 208 6 "z2-z1;" }{MPLTEXT 1 208 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 203 "" 0 "" {TEXT 207 3 "09." }{TEXT 207 0 "" }}}{EXCHG {PARA 204 "> " 0 "" {MPLTEXT 1 208 14 "start:=time():" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 19 "\nz3: =multiply(x,y):" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 14 "\ntime()-sta rt;" }{MPLTEXT 1 208 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"$q$!\"$ " }}}{EXCHG {PARA 203 "" 0 "" {TEXT 207 3 "10." }{TEXT 207 0 "" }}} {EXCHG {PARA 204 "> " 0 "" {MPLTEXT 1 208 30 "rnd:=rand(10^99999,10^10 0000):" }{MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 10 "\nx:=rnd():" } {MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 10 "\ny:=rnd():" }{MPLTEXT 1 208 0 "" }}}{EXCHG {PARA 203 "" 0 "" {TEXT 207 3 "11." }{TEXT 207 0 "" }}} {EXCHG {PARA 204 "> " 0 "" {MPLTEXT 1 208 14 "start:=time():" } {MPLTEXT 1 208 0 "" }{MPLTEXT 1 208 5 "\nx*y:" }{MPLTEXT 1 208 0 "" } {MPLTEXT 1 208 14 "\ntime()-start;" }{MPLTEXT 1 208 0 "" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#$\"$@&!\"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 205 "" 0 "" {TEXT 203 0 "" }}{PARA 205 "" 0 "" {TEXT 203 0 "" }}{PARA 205 "" 0 "" {TEXT 203 0 "" }}{PARA 205 "" 0 "" {TEXT 203 0 "" }}{PARA 206 "" 0 "" {TEXT 209 0 "" }}{PARA 207 "" 0 "" {TEXT -1 0 "" }}}{MARK "1 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }