{VERSION 5 0 "IBM INTEL NT" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 2 1 2 0 0 0 1 }{CSTYLE "_cstyle1" -1 202 "Times" 0 1 0 0 0 0 0 0 0 2 2 2 0 0 0 1 }{CSTYLE "_cstyle2" -1 203 "Times" 0 1 0 0 0 0 0 0 0 2 2 2 0 0 0 1 }{PSTYLE "_pstyle1" -1 200 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 }{PSTYLE "_pstyle 2" -1 201 1 {CSTYLE "" -1 -1 "Courier" 0 1 255 0 0 1 0 1 0 2 1 2 0 0 0 1 }0 0 0 -1 -1 -1 1 0 1 0 2 2 -1 1 }{PSTYLE "_pstyle3" -1 202 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 200 "" 0 "" {TEXT 202 3 "01." }{TEXT 202 0 "" }}} {EXCHG {PARA 201 "> " 0 "" {MPLTEXT 1 0 38 "with(PolynomialTools):with (ListTools):" }{MPLTEXT 1 0 0 "" }{MPLTEXT 1 0 1 "\n" }{MPLTEXT 1 0 39 "\nPolynomialKaratsuba:=proc(pol1,pol2,x)" }{MPLTEXT 1 0 0 "" } {MPLTEXT 1 0 27 "\nlocal list1,list2,list3,l;" }{MPLTEXT 1 0 0 "" } {MPLTEXT 1 0 57 "\nlist1:=Reverse(convert(CoefficientVector(pol1,x),li st));" }{MPLTEXT 1 0 0 "" }{MPLTEXT 1 0 57 "\nlist2:=Reverse(convert(C oefficientVector(pol2,x),list));" }{MPLTEXT 1 0 0 "" }{MPLTEXT 1 0 35 "\nlist3:=ListKaratsuba(list1,list2);" }{MPLTEXT 1 0 0 "" }{MPLTEXT 1 0 16 "\nl:=nops(list3);" }{MPLTEXT 1 0 0 "" }{MPLTEXT 1 0 29 "\nsum(li st3[l-k]*x^k,k=0..l-1)" }{MPLTEXT 1 0 0 "" }{MPLTEXT 1 0 10 "\nend pro c:" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 200 "" 0 "" {TEXT 202 3 "02." } {TEXT 202 0 "" }}}{EXCHG {PARA 201 "> " 0 "" {MPLTEXT 1 0 32 "ListKara tsuba:=proc(list1,list2)" }{MPLTEXT 1 0 0 "" }{MPLTEXT 1 0 17 "\noptio n remember;" }{MPLTEXT 1 0 0 "" }{MPLTEXT 1 0 70 "\nlocal n,m,nn,mm,a, b,c,d,list1neu,list2neu,amalc,bmald,tab,mittelterm;" }{MPLTEXT 1 0 0 " " }{MPLTEXT 1 0 35 "\nif min(nops(list1),nops(list2))=1 " }{MPLTEXT 1 0 0 "" }{MPLTEXT 1 0 33 "\n then return(list1[1]*list2[1])" } {MPLTEXT 1 0 0 "" }{MPLTEXT 1 0 24 "\n else nn:=nops(list1);" } {MPLTEXT 1 0 0 "" }{MPLTEXT 1 0 24 "\n mm:=nops(list2);" } {MPLTEXT 1 0 0 "" }{MPLTEXT 1 0 22 "\n m:=max(nn,mm);" } {MPLTEXT 1 0 0 "" }{MPLTEXT 1 0 13 "\n n:=1;" }{MPLTEXT 1 0 0 " " }{MPLTEXT 1 0 35 "\n while n " 0 "" {MPLTEXT 1 0 45 "Polynomi alKaratsuba(3*x^2+2*x-1,5*x^3+x+2,x);" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 200 "" 0 "" {TEXT 202 3 "04." }{TEXT 202 0 "" }}}{EXCHG {PARA 201 "> " 0 "" {MPLTEXT 1 0 34 "expand((3*x^2+2*x-1)*(5*x^3+x+2));" } {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 200 "" 0 "" {TEXT 202 3 "05." } {TEXT 202 0 "" }}}{EXCHG {PARA 201 "> " 0 "" {MPLTEXT 1 0 17 "rnd:=ran d(1..10):" }{MPLTEXT 1 0 0 "" }{MPLTEXT 1 0 46 "\npol1:=convert([seq(r nd()*x^k,k=0..100)],`+`):" }{MPLTEXT 1 0 0 "" }{MPLTEXT 1 0 46 "\npol2 :=convert([seq(rnd()*x^k,k=0..100)],`+`):" }{MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 200 "" 0 "" {TEXT 202 3 "06." }{TEXT 202 0 "" }}}{EXCHG {PARA 201 "> " 0 "" {MPLTEXT 1 0 14 "start:=time():" }{MPLTEXT 1 0 0 " " }{MPLTEXT 1 0 26 "\nprod1:=expand(pol1*pol2):" }{MPLTEXT 1 0 0 "" } {MPLTEXT 1 0 16 "\ntime()-start();" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 200 "" 0 "" {TEXT 202 3 "07." }{TEXT 202 0 "" }}}{EXCHG {PARA 201 "> " 0 "" {MPLTEXT 1 0 14 "start:=time():" }{MPLTEXT 1 0 0 "" } {MPLTEXT 1 0 41 "\nprod2:=PolynomialKaratsuba(pol1,pol2,x):" } {MPLTEXT 1 0 0 "" }{MPLTEXT 1 0 16 "\ntime()-start();" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 200 "" 0 "" {TEXT 202 3 "08." }{TEXT 202 0 "" }}} {EXCHG {PARA 201 "> " 0 "" {MPLTEXT 1 0 12 "prod2-prod1;" }{MPLTEXT 1 0 0 "" }}}{PARA 202 "" 0 "" {TEXT 203 0 "" }}{PARA 202 "" 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 }