{VERSION 7 1 "Linux" "7.1" } {USTYLETAB {PSTYLE "Ordered List 5" -1 200 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 3 3 2 144 2 0 2 2 -1 1 } {PSTYLE "Heading 4" -1 20 1 {CSTYLE "" -1 -1 "MS Serif" 1 12 0 0 0 1 1 2 2 2 2 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Text Output " -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 12 0 0 255 1 2 2 2 2 2 1 3 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Ordered List 1" -1 201 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 3 3 2 0 2 0 2 2 -1 1 }{PSTYLE "Bullet Item" -1 15 1 {CSTYLE "" -1 -1 "Tim es" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 0 2 0 2 2 -1 1 } {PSTYLE "Author" -1 19 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }3 1 0 0 8 8 2 0 2 0 2 2 -1 1 }{PSTYLE "Dash Item" -1 16 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 3 3 2 0 2 0 2 2 -1 1 }{PSTYLE "Heading 3" -1 5 1 {CSTYLE "" -1 -1 "MS S erif" 1 14 0 0 0 1 1 1 2 2 2 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 } {PSTYLE "Diagnostic" -1 9 1 {CSTYLE "" -1 -1 "Courier" 1 12 40 120 40 1 2 2 2 2 2 1 2 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Ordered \+ List 4" -1 202 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 3 3 2 108 2 0 2 2 -1 1 }{PSTYLE "Maple Output" -1 11 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "List Item" -1 14 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 3 3 2 0 2 0 2 2 -1 1 } {PSTYLE "Line Printed Output" -1 6 1 {CSTYLE "" -1 -1 "Courier" 1 12 0 0 255 1 2 2 2 2 2 1 2 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "H eading 2" -1 4 1 {CSTYLE "" -1 -1 "MS Serif" 1 16 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }1 1 0 0 8 2 2 0 2 0 2 2 -1 1 }{PSTYLE "Ordered List 3" -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 3 3 2 72 2 0 2 2 -1 1 }{PSTYLE "Error" -1 8 1 {CSTYLE "" -1 -1 "Courie r" 1 12 255 0 255 1 2 2 2 2 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Maple Plot" -1 13 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Warning" -1 7 1 {CSTYLE "" -1 -1 "Courier" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Heading 1" -1 3 1 {CSTYLE "" -1 -1 "MS Serif" 1 18 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }1 1 0 0 8 4 2 0 2 0 2 2 -1 1 }{PSTYLE "Title" -1 18 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }3 1 0 0 12 12 2 0 2 0 2 2 -1 1 }{PSTYLE "Ordered Li st 2" -1 204 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 3 3 2 36 2 0 2 2 -1 1 }{PSTYLE "Normal" -1 0 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 }{CSTYLE "Equation Label" -1 200 "Courier" 1 12 0 0 0 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "Text" -1 201 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "Page Number" -1 33 "Times" 1 10 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "Maple Input" -1 0 "Courier" 1 12 255 0 0 1 2 1 2 2 1 2 0 0 0 1 }{CSTYLE "2D Output" -1 20 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 0 0 0 1 }{CSTYLE "Dictionary Hyperlink" -1 45 "MS Serif" 1 12 147 0 15 1 2 2 1 2 2 2 0 0 0 1 }{CSTYLE "2D Input" -1 19 "Times" 1 12 0 0 0 1 2 2 2 2 1 2 0 0 0 1 }{CSTYLE "Maple Input Placeholder" -1 202 "Couri er" 1 12 200 0 200 1 2 1 2 2 1 2 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Time s" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "Hyperlink" -1 17 "MS Ser if" 1 12 0 128 128 1 2 2 1 2 2 2 0 0 0 1 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT 203 29 "Komputeralgebrai algorit musok" }}}{EXCHG {PARA 19 "" 0 "" {TEXT 204 18 "J\303\241rai Antal" }} }{EXCHG {PARA 19 "" 0 "" {TEXT 201 69 "Ezek a programok csak szeml\303 \251ltet\303\251sre szolg\303\241lnak." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 4 "1. T" }{TEXT 205 18 "\303\266rt\303\251" }{TEXT 205 3 "ne t" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 18 "2. Algebrai alapok" }}} {SECT 1 {PARA 3 "" 0 "" {TEXT 205 7 "3. Norm" }{TEXT 205 8 "\303\241" }{TEXT 205 6 "l form" }{TEXT 205 8 "\303\241" }{TEXT 205 12 "k, reprez ent" }{TEXT 205 18 "\303\241ci\303\263" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT 205 13 "4. Aritmetika" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 19 "A 4.1. Algoritm us. " }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "BigIntegerMultiply:=proc(a,b,B) local c,t,i,j,carry; \n" }{MPLTEXT 1 0 56 " c:=[]; for i from 0 to nops(a)-1 do c:=[op(c), 0] od;\n" }{MPLTEXT 1 0 32 " for j from 0 to nops(b)-1 do\n" } {MPLTEXT 1 0 15 " carry:=0;\n" }{MPLTEXT 1 0 34 " for i from 0 t o nops(a)-1 do\n" }{MPLTEXT 1 0 40 " t:=a[i+1]*b[j+1]+c[i+j+1]+ca rry;\n" }{MPLTEXT 1 0 25 " carry:=iquo(t,B);\n" }{MPLTEXT 1 0 27 " c[i+j+1]:=irem(t,B)\n" }{MPLTEXT 1 0 9 " od;\n" }{MPLTEXT 1 0 23 " c:=[op(c),carry];\n" }{MPLTEXT 1 0 10 " od; c;\n" }{MPLTEXT 1 0 6 "end;\n" }{MPLTEXT 1 0 1 " " }}{PARA 11 "" 1 "" {XPPMATH 20 "f* 6%I\"aG6\"I\"bGF%I\"BGF%6'I\"cGF%I\"tGF%I\"iGF%I\"jGF%I&carryGF%F%F%C& >F)7\"?(F+\"\"!\"\"\",&-I%nopsG%*protectedG6#F$F3F3!\"\"I%trueGF7>F)7$ -I#opGF76#F)F2?(F,F2F3,&-F66#F&F3F3F9F:C%>F-F2?(F+F2F3F4F:C%>F*,(*&&F$ 6#,&F+F3F3F3F3&F&6#,&F,F3F3F3F3F3&F)6#,(F+F3F,F3F3F3F3F-F3>F--I%iquoGF 76$F*F'>FQ-I%iremGF7FW>F)7$F=F-F)F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 70 "a:=floor(evalf(10^10*Pi,20)); b:=floor(evalf(10^10*ex p(1))); c:=a*b;\n" }{MPLTEXT 1 0 74 "a:=convert(a,base,10^4); b:=conve rt(b,base,10^4); c:=convert(c,base,10^4);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\",Nl#fTJ" }}{PARA 11 "" 1 "" {XPPMATH 20 "\",!G=G=F" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"6+)f]t)4AM(R&)" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"%Nl\"%#f\"\"$9$" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\" %!G)\"%\"G)\"$r#" }}{PARA 11 "" 1 "" {XPPMATH 20 "7(\"%+)*\"%0N\"$()* \"%AM\"%(R&\"\")" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "BigInte gerMultiply(a,b,10^4);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7(\"%+)*\"%0N \"$()*\"%AM\"%(R&\"\")" }}}{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#% ?G" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 8 "E 4.1. P" }{TEXT 206 12 " \303\251lda." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "with(powseries);" }}{PARA 11 "" 1 "" {XPPMATH 20 "77I(composeG6\"I(evalpowGF$I(inverseGF$I*multconstGF$I)multiplyGF$I)n egativeG%*protectedGI'powaddGF$I'powcosGF$I*powcreateGF$I(powdiffGF$I' powexpGF$I'powintGF$I'powlogGF$I(powpolyGF$I'powsinGF$I)powsolveGF$I(p owsqrtGF$I)quotientGF$I*reversionGF$I)subtractGF$I(tpsformGF$" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "a:=powpoly((1-x)^5,x); tpsfo rm(a,x,8);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I(powparmG6\"6$I#nnGF% I#t1GF%6#IaoCopyright~(c)~1990~by~the~University~of~Waterloo.~All~righ ts~reserved.GF%E\\s(\"\"!\"\"\"F-!\"&\"\"#\"#5\"\"$!#5\"\"&!\"\"\"\"%F 3I#_kGF%F,C$@%-I%typeG%*protectedG6$F$I(integerGF;C$>F'-%)procnameG6#F 6@%30-I#opGF;6$F5-FG6#FAI%NULLGF;-I$hasGF;6$7#-I(indicesGF;6#FFF6C%>F( -I%subsGF;6$/F6F$F'>-FA6#%%argsG-I%evalGF;6#F(OFgnO.FZC$>FZF\\oF[o7%I( powpolyG6$F;/I+modulenameGF%I*powseriesG6$F;I(_syslibGF%*$),&F-F-I\"xG F%F4F3F-FjoF%F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "+/I\"xG6\"\"\"\"\" \"!!\"&F%\"#5\"\"#!#5\"\"$\"\"&\"\"%!\"\"F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "b:=inverse(a); tpsform(b,x,8);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I(powparmG6\"6$I#nnGF%I#t1GF%6#IaoCopyright~(c)~1990 ~by~the~University~of~Waterloo.~All~rights~reserved.GF%E\\s#\"\"!\"\" \"I#_kGF%,$-I$sumGF%6$*&-I\"aGF%6#I\"jGF%F--I$ansGF%6#,&F.F-F7!\"\"F-/ F7;F-F.FF'-%)procnameG6#F. @%30-I#opGFC6$\"\"%-FO6#FII%NULLGFC-I$hasGFC6$7#-I(indicesGFC6#FNF.C%> F(-I%subsGFC6$/F.F$F'>-FI6#%%argsG-I%evalGFC6#F(OF`oO.F]oC$>F]oFeoFdo7 $I(inverseG6$FC/I+modulenameGF%I*powseriesG6$FCI(_syslibGF%F5F%F%F%" } }{PARA 11 "" 1 "" {XPPMATH 20 "+5I\"xG6\"\"\"\"\"\"!\"\"&F%\"#:\"\"#\" #N\"\"$\"#q\"\"%\"$E\"F'\"$5#\"\"'\"$I$\"\"(-I\"OG%*protectedG6#F%\"\" )" }}}{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#%?G" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 8 "E 4.2. P" }{TEXT 206 12 "\303\251lda." }} {PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "a:=powpoly(x,x); b:=powsin(a); tpsform(b,x,8);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I(powparmG6\"6$I#nnGF%I#t1GF%6#IaoCopyright~(c)~19 90~by~the~University~of~Waterloo.~All~rights~reserved.GF%E\\s#\"\"\"F, I#_kGF%\"\"!C$@%-I%typeG%*protectedG6$F$I(integerGF3C$>F'-%)procnameG6 #F-@%30-I#opGF36$\"\"%-F?6#F9I%NULLGF3-I$hasGF36$7#-I(indicesGF36#F>F- C%>F(-I%subsGF36$/F-F$F'>-F96#%%argsG-I%evalGF36#F(OFVO.FSC$>FSFenFZ7% I(powpolyG6$F3/I+modulenameGF%I*powseriesG6$F3I(_syslibGF%I\"xGF%F`oF% F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I(powparmG6\"6$I#nnGF%I#t1GF %6#IaoCopyright~(c)~1990~by~the~University~of~Waterloo.~All~rights~res erved.GF%E\\s#\"\"!F,I#_kGF%*&-I$sumG6$%*protectedGI(_syslibGF%6$*(I\" iGF%\"\"\"-I\"aGF%6#F6F7-I'anscosGF%6#,&F-F7F6!\"\"F7/F6;F7F-F7F-F?C$@ %-I%typeGF26$F$I(integerGF2C$>F'-%)procnameG6#F-@%30-I#opGF26$\"\"%-FQ 6#FKI%NULLGF2-I$hasGF26$7#-I(indicesGF26#FPF-C%>F(-I%subsGF26$/F-F$F'> -FK6#%%argsG-I%evalGF26#F(OFboO.F_oC$>F_oFgoFfo7$I'powsinG6$F2/I+modul enameGF%I*powseriesGF1F9F%F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "+-I\"x G6\"\"\"\"F%#!\"\"\"\"'\"\"$#F%\"$?\"\"\"&#F'\"%S]\"\"(-I\"OG%*protect edG6#F%\"\")" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "c:=reversio n(b); tpsform(c,x,8);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I(powparmG6 \"6$I#nnGF%I#t1GF%6#IaoCopyright~(c)~1990~by~the~University~of~Waterlo o.~All~rights~reserved.GF%E\\s%\"\"!F,\"\"\"F-I#_kGF%-I*_powreverGI':- 6386GQC/home/ajarai/maple10/lib/maple.mlaF%6%I\"bGF%F.I$ansGF%I._powin tervalsGF%=F%I&falseG%*protectedGE\\[l\"6$F-F-F-C$@%-I%typeGF96$F$I(in tegerGF9C$>F'-%)procnameG6#F.@%30-I#opGF96$\"\"%-FK6#FEI%NULLGF9-I$has GF96$7#-I(indicesGF96#FJF.C%>F(-I%subsGF96$/F.F$F'>-FE6#%%argsG-I%eval GF96#F(OF\\oO.FinC$>FinFaoF`o7$I*reversionG6$F9/I+modulenameGF%I*powse riesG6$F9I(_syslibGF%F4F%F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "+-I\"xG 6\"\"\"\"F%#F%\"\"'\"\"$#F(\"#S\"\"&#F+\"$7\"\"\"(-I\"OG%*protectedG6# F%\"\")" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#%?G" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 19 "A 4.2. Algoritmus. " }}{PARA 0 "" 0 "" {TEXT 201 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 70 "Karatsuba:=proc(a,b,n,B) loc al aa,bb,a1,a2,b1,b2,n1,n2,c1,c2,c3,c,t;\n" }{MPLTEXT 1 0 23 " c:=sig n(a)*sign(b);\n" }{MPLTEXT 1 0 27 " aa:=abs(a); bb:=abs(b);\n" } {MPLTEXT 1 0 15 " if n=1 then\n" }{MPLTEXT 1 0 41 " t:=BigIntegerM ultiply([aa],[bb],B);\n" }{MPLTEXT 1 0 28 " return c*(t[2]*B+t[1]) \n" }{MPLTEXT 1 0 7 " fi;\n" }{MPLTEXT 1 0 29 " n1:=floor(n/2); n2:= n-n1;\n" }{MPLTEXT 1 0 41 " a1:=iquo(aa,B^n1); a2:=irem(aa,B^n1);\n" }{MPLTEXT 1 0 41 " b1:=iquo(bb,B^n1); b2:=irem(bb,B^n2);\n" }{MPLTEXT 1 0 30 " c1:=Karatsuba(a1,b1,n1,B);\n" }{MPLTEXT 1 0 36 " c2:=Karat suba(a1-a2,b2-b1,n2,B);\n" }{MPLTEXT 1 0 30 " c3:=Karatsuba(a2,b2,n2, B);\n" }{MPLTEXT 1 0 39 " c*(c1*B^(2*n1)+(c1+c2+c3)*B^n1+c3);\n" } {MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I\"aG6\"I\"b GF%I\"nGF%I\"BGF%6/I#aaGF%I#bbGF%I#a1GF%I#a2GF%I#b1GF%I#b2GF%I#n1GF%I# n2GF%I#c1GF%I#c2GF%I#c3GF%I\"cGF%I\"tGF%F%F%C0>F5*&-I%signG%*protected G6#F$\"\"\"-F;6#F&F>>F*-I$absGFF+-FCF@@$/F'F>C$>F6-I3BigIntegerMul tiplyGF%6%7#F*7#F+F(O*&F5F>,&*&&F66#\"\"#F>F(F>F>&F66#F>F>F>>F0-I&floo rG6$FFUF>F'F>F>>F1,&F'F>F0!\"\">F,-I%iquoGF<6$F* )F(F0>F--I%iremGFF.-F`o6$F+Fbo>F/-Feo6$F+)F(F1>F2-I*KaratsubaGF%6 &F,F.F0F(>F3-F_p6&,&F,F>F-F]o,&F/F>F.F]oF1F(>F4-F_p6&F-F/F1F(*&F5F>,(* &F2F>)F(,$*&FUF>F0F>F>F>F>*&,(F2F>F3F>F4F>F>FboF>F>F4F>F>F%F%F%" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 70 "a:=floor(evalf(10^10*Pi,20)) ; b:=floor(evalf(10^10*exp(1))); c:=a*b;\n" }{MPLTEXT 1 0 40 "debug(Ka ratsuba); Karatsuba(a,b,3,10^4);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\",N l#fTJ" }}{PARA 11 "" 1 "" {XPPMATH 20 "\",!G=G=F" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"6+)f]t)4AM(R&)" }}{PARA 11 "" 1 "" {XPPMATH 20 "I*Karat subaG6\"" }}{PARA 9 "" 1 "" {TEXT 207 64 "\{--> enter Karatsuba, args \+ = 31415926535, 27182818280, 3, 10000" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\",Nl#fTJ" }}{PARA 11 "" 1 "" {XPPMATH 20 "\",!G=G=F" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"(#fTJ" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%Nl" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"(\"G=F" }}{PARA 11 "" 1 "" {XPPMATH 20 "\")!G=G)" }} {PARA 9 "" 1 "" {TEXT 207 56 "\{--> enter Karatsuba, args = 3141592, 2 718281, 1, 10000" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 " " 1 "" {XPPMATH 20 "\"(#fTJ" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"(\"G=F" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$\"%_L\"*%)H(R&)" }}{PARA 9 "" 1 "" {TEXT 207 55 "<-- exit Karatsuba (now in Karatsuba) = 8539729843352\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"._L%)H(R&)" }}{PARA 9 "" 1 "" {TEXT 207 57 "\{--> enter Karatsuba, args = 3135057, 80099999, 2, 10000" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"(d]8$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\")****4!)" }}{PARA 11 "" 1 " " {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"$8$" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"%d]" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%4!)" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%****" }}{PARA 9 "" 1 "" {TEXT 207 49 "\{--> enter Kara tsuba, args = 313, 8009, 1, 10000" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" \"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$8$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%4!)" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$\"% enter Karatsuba, args = 4744, 1990, 1, 10000" }} {PARA 11 "" 1 "" {XPPMATH 20 "!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"%WZ" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%!*>" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$\"$g&\"$W*" }}{PARA 9 "" 1 "" {TEXT 207 49 "<-- exit Ka ratsuba (now in Karatsuba) = 9440560\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "!(g0W*" }}{PARA 9 "" 1 "" {TEXT 207 50 "\{--> enter Karatsuba, args \+ = 5057, 9999, 1, 10000" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"%d]" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"%****" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$\"%V\\\"%c]" }}{PARA 9 "" 1 "" {TEXT 207 50 "<-- exit Karatsuba (now in Karatsuba) = 50564943\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "\")V\\c]" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"0V\\ci!=6D" }}{PARA 9 "" 1 "" {TEXT 207 57 "<-- exit Karatsuba ( now in Karatsuba) = 251118062564943\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"0V\\ci!=6D" }}{PARA 9 "" 1 "" {TEXT 207 54 "\{--> enter Karatsuba, \+ args = 6535, 82818280, 2, 10000" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\" \"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%Nl" }}{PARA 11 "" 1 "" {XPPMATH 20 "\")!G=G)" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%Nl" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%\"G)" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%!G)" }}{PARA 9 "" 1 "" {TEXT 207 47 "\{--> enter Karatsuba, args = 0, 8281, 1, 1000 0" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%\"G)" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$\"\"!F#" }}{PARA 9 "" 1 "" {TEXT 207 43 "<-- exit Karatsuba (now in Karatsuba) = 0\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 9 "" 1 "" {TEXT 207 47 "\{--> enter Karatsuba, args = 6535, 1, 1, 10000" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%Nl" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$\"%Nl\"\"!" }}{PARA 9 "" 1 "" {TEXT 207 46 "<-- exit Karatsuba (now in Karatsuba) = 6535\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%Nl" }}{PARA 9 "" 1 "" {TEXT 207 50 "\{--> enter \+ Karatsuba, args = 6535, 8280, 1, 10000" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%Nl" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%!G)" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$\"%+)*\"%5a" }} {PARA 9 "" 1 "" {TEXT 207 50 "<-- exit Karatsuba (now in Karatsuba) = \+ 54109800\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "\")+)4T&" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"-+)fu@T&" }}{PARA 9 "" 1 "" {TEXT 207 54 "<-- exit K aratsuba (now in Karatsuba) = 541217459800\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"-+)fu@T&" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"6+)4%)4v\\( \\dc)" }}{PARA 9 "" 1 "" {TEXT 207 63 "<-- exit Karatsuba (now at top \+ level) = 856574974975098409800\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"6+ )4%)4v\\(\\dc)" }}}{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#%?G" }}}} {SECT 0 {PARA 4 "" 0 "" {TEXT 206 19 "A 4.3. Algoritmus. " }}{PARA 0 " " 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "with (CurveFitting);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7*I(BSplineG6\"I-BSpl ineCurveGF$I,InteractiveGF$I-LeastSquaresGF$I8PolynomialInterpolationG F$I6RationalInterpolationGF$I'SplineGF$I4ThieleInterpolationGF$" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "TrialDivision:=proc(a,b,x,L) local i,c,y,La,Lb;\n" }{MPLTEXT 1 0 30 " La:=map(y->subs(x=y,a),L); \n" }{MPLTEXT 1 0 30 " Lb:=map(y->subs(x=y,b),L);\n" }{MPLTEXT 1 0 23 " for i to nops(L) do\n" }{MPLTEXT 1 0 21 " if Lb[i]=0 then\n" }{MPLTEXT 1 0 53 " if La[i]<>0 then return FAIL else La[i]=0 fi; \n" }{MPLTEXT 1 0 33 " else La[i]:=La[i]/Lb[i] fi;\n" }{MPLTEXT 1 0 7 " od;\n" }{MPLTEXT 1 0 39 " c:=PolynomialInterpolation(L,La,x); \n" }{MPLTEXT 1 0 63 " if degree(c,x)=degree(a,x)-degree(b,x) then c \+ else FAIL fi;\n" }{MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I\"aG6\"I\"bGF%I\"xGF%I\"LGF%6'I\"iGF%I\"cGF%I\"yGF%I#LaGF%I#LbG F%F%F%C'>F--I$mapG%*protectedG6$f*6#F,F%6$I)operatorGF%I&arrowGF%F%-I% subsGF36$/F'F,F$F%F%6&F'9&F$9$F(>F.-F26$f*F6F%F7F%-F;6$F=F&F%F%6&F'F?F &9%F(?(F*\"\"\"FJ-I%nopsGF36#F(I%trueGF3@%/&F.6#F*\"\"!@%0&F-FRFSOI%FA ILGF3/FVFS>FV*&FVFJFQ!\"\">F+-_I-CurveFittingG6$F3I(_syslibGF%I8Polyno mialInterpolationGF%6%F(F-F'@%/-I'degreeGF36$F+F',&-Fbo6$F$F'FJ-Fbo6$F &F'FfnF+FXF%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "b:=3*x^ 3-4*x^2+x-3; c:=6*x^2+2*x-7; a:=expand(b*c); L:=[i$i=0..5];" }}{PARA 11 "" 1 "" {XPPMATH 20 ",**&\"\"$\"\"\")I\"xG6\"F$F%F%*&\"\"%F%)F'\"\" #F%!\"\"F'F%F$F-" }}{PARA 11 "" 1 "" {XPPMATH 20 ",(*&\"\"'\"\"\")I\"x G6\"\"\"#F%F%*&F)F%F'F%F%\"\"(!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 ", .*&\"#=\"\"\")I\"xG6\"\"\"&F%F%*&F$F%)F'\"\"%F%!\"\"*&\"#BF%)F'\"\"$F% F-*&\"#7F%)F'\"\"#F%F%*&\"#8F%F'F%F-\"#@F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "7(\"\"!\"\"\"\"\"#\"\"$\"\"%\"\"&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "debug(TrialDivision); TrialDivision(a,b,x,L);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I.TrialDivisionG6\"" }}{PARA 9 "" 1 "" {TEXT 207 109 "\{--> enter TrialDivision, args = 18*x^5-18*x^4-23*x^3 +12*x^2-13*x+21, 3*x^3-4*x^2+x-3, x, [0, 1, 2, 3, 4, 5]" }}{PARA 11 "" 1 "" {XPPMATH 20 "7(\"#@!\"$\"$Z\"\"%&Q#\"&8D\"\"&\"QU" }}{PARA 11 "" 1 "" {XPPMATH 20 "7(!\"$F#\"\"(\"#X\"$H\"\"$x#" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#@" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#`" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"#(*" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"$`\"" }}{PARA 11 "" 1 "" {XPPMATH 20 ",(*&\"\"'\"\"\")I\"xG6\"\"\"#F %F%*&F)F%F'F%F%\"\"(!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 ",(*&\"\"'\" \"\")I\"xG6\"\"\"#F%F%*&F)F%F'F%F%\"\"(!\"\"" }}{PARA 9 "" 1 "" {TEXT 207 57 "<-- exit TrialDivision (now at top level) = 6*x^2+2*x-7\}" }} {PARA 11 "" 1 "" {XPPMATH 20 ",(*&\"\"'\"\"\")I\"xG6\"\"\"#F%F%*&F)F%F 'F%F%\"\"(!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "a:=a-1; \+ TrialDivision(a,b,x,L);" }}{PARA 11 "" 1 "" {XPPMATH 20 ",.*&\"#=\"\" \")I\"xG6\"\"\"&F%F%*&F$F%)F'\"\"%F%!\"\"*&\"#BF%)F'\"\"$F%F-*&\"#7F%) F'\"\"#F%F%*&\"#8F%F'F%F-F$F%" }}{PARA 9 "" 1 "" {TEXT 207 109 "\{--> \+ enter TrialDivision, args = 18*x^5-18*x^4-23*x^3+12*x^2-13*x+18, 3*x^3 -4*x^2+x-3, x, [0, 1, 2, 3, 4, 5]" }}{PARA 11 "" 1 "" {XPPMATH 20 "7( \"#=!\"'\"$W\"\"%#Q#\"&5D\"\"&yB%" }}{PARA 11 "" 1 "" {XPPMATH 20 "7(! \"$F#\"\"(\"#X\"$H\"\"$x#" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"'" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "# \"$W\"\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "#\"$%z\"#:" }}{PARA 11 "" 1 "" {XPPMATH 20 "#\"%qT\"#V" }}{PARA 11 "" 1 "" {XPPMATH 20 "#\"&yB% \"$x#" }}{PARA 11 "" 1 "" {XPPMATH 20 ",.*&#\"'<:C\"(l>v$\"\"\")I\"xG6 \"\"\"&F'F'*&#\"',4O\"'&)oTF')F)\"\"%F'!\"\"*&#\"))oja\"F&F')F)\"\"$F' F'*&#\"'\\s#)F/F')F)\"\"#F'F2*&#\"(t2+&\"'$R](F'F)F'F'\"\"'F2" }} {PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protectedG" }}{PARA 9 "" 1 "" {TEXT 207 50 "<-- exit TrialDivision (now at top level) = FAIL\}" }} {PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protectedG" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 8 "E 4.3. P" }{TEXT 206 12 "\303\251lda." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "om ega:=(1+I)/sqrt(2); omega^8; omega^4;" }}{PARA 11 "" 1 "" {XPPMATH 20 "*&,&#\"\"\"\"\"#F%*&F$F%^#F%F%F%F%)F&F$F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "omega:=I; omega^8; omega^4;" }} {PARA 11 "" 1 "" {XPPMATH 20 "^#\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}}{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#%?G" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 8 "E 4.4. P" }{TEXT 206 12 "\303\251lda." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "4^4 mod 17; [4^i$i=0..3 ] mod 17;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"\"\"\"\"%\"#;\"#8" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "A:=Matrix(4,(i,j)->4^((i-1)*(j-1)) mod 17);" }}{PARA 11 "" 1 "" {XPPMATH 20 "-I'MatrixG6$%*protectedGI(_syslibG6\"6#/I$%idG F'\"*GO@^\"" }}}{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#%?G" }}}} {SECT 0 {PARA 4 "" 0 "" {TEXT 206 8 "E 4.5. P" }{TEXT 206 12 "\303\251 lda." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "`mod`:=mods;" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%modsG %*protectedG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "14&^8 mod 4 1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 35 "[14&^i$i=0..7]; map(x->x mod 41,%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7*-I#&^G6\"6$\"#9\"\"!-F$6$F'\"\"\"-F$6$F'\"\"#-F$6$ F'\"\"$-F$6$F'\"\"%-F$6$F'\"\"&-F$6$F'\"\"'-F$6$F'\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "7*\"\"\"\"#9!\"*!\"$!\"\"!#9\"\"*\"\"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "[(-9)&^i$i=0..3]; map(x->x mod 41,% );" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&-I#&^G6\"6$!\"*\"\"!-F$6$F'\"\" \"-F$6$F'\"\"#-F$6$F'\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"\"\"! \"*!\"\"\"\"*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "[(-1)&^i$i =0..1]; map(x->x mod 41,%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$-I#&^G6 \"6$!\"\"\"\"!-F$6$F'\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$\"\"\"! \"\"" }}}{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#%?G" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 8 "E 4.6. P" }{TEXT 206 12 "\303\251lda." }} {PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "a:=5*x^6+x^5+3*x^3+x^2-4*x+1;" }}{PARA 11 "" 1 "" {XPPMATH 20 ", .*&\"\"&\"\"\")I\"xG6\"\"\"'F%F%*$)F'F$F%F%*&\"\"$F%)F'F-F%F%*$)F'\"\" #F%F%*&\"\"%F%F'F%!\"\"F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "b:=5*y^3+y+1; c:=y^2+3*y-4; a=expand(subs(y=x^2,b+x*c));" }}{PARA 11 "" 1 "" {XPPMATH 20 ",(*&\"\"&\"\"\")I\"yG6\"\"\"$F%F%F'F%F%F%" }} {PARA 11 "" 1 "" {XPPMATH 20 ",(*$)I\"yG6\"\"\"#\"\"\"F(*&\"\"$F(F%F(F (\"\"%!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "/,.*&\"\"&\"\"\")I\"xG6\" \"\"'F&F&*$)F(F%F&F&*&\"\"$F&)F(F.F&F&*$)F(\"\"#F&F&*&\"\"%F&F(F&!\"\" F&F&F#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "d:=1; e:=5*z+1; b =expand(subs(z=y^2,d+y*e));" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" } }{PARA 11 "" 1 "" {XPPMATH 20 ",&*&\"\"&\"\"\"I\"zG6\"F%F%F%F%" }} {PARA 11 "" 1 "" {XPPMATH 20 "/,(*&\"\"&\"\"\")I\"yG6\"\"\"$F&F&F(F&F& F&F#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "subs(z=1,d) mod 41; subs(z=1,e) mod 41;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "subs(y=1,b) mod 41=1+1*6 mod 41; subs(y=-1,b) mod 41=1-1*6 mod 4 1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "/\"\"(F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "/!\"&F#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "sub s(z=-1,d) mod 41; subs(z=-1,e) mod 41;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 75 "subs(y=-9,b) mod 41=1+(-9)*(-4) mod 41; subs(y= 9,b) mod 41=1+9*(-4) mod 41;" }}{PARA 11 "" 1 "" {XPPMATH 20 "/!\"%F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "/\"\"'F#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "subs(y=1,c) mod 41; subs(y=-1,c) mod 41;\n" } {MPLTEXT 1 0 40 "subs(y=-9,c) mod 41; subs(y=9,c) mod 41;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"'" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "! #>" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "subs(x=3,a) mod 41=6+ 3*(-19) mod 41;\n" }{MPLTEXT 1 0 40 "subs(x=-3,a) mod 41=6+(-3)*(-19) \+ mod 41;" }}{PARA 11 "" 1 "" {XPPMATH 20 "/!#5F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "/!#>F#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "[14& ^i$i=0..7]; map(x->x mod 41,%); map(y->subs(x=y,a) mod 41,%);" }} {PARA 11 "" 1 "" {XPPMATH 20 "7*-I#&^G6\"6$\"#9\"\"!-F$6$F'\"\"\"-F$6$ F'\"\"#-F$6$F'\"\"$-F$6$F'\"\"%-F$6$F'\"\"&-F$6$F'\"\"'-F$6$F'\"\"(" } }{PARA 11 "" 1 "" {XPPMATH 20 "7*\"\"\"\"#9!\"*!\"$!\"\"!#9\"\"*\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "7*\"\"(!\"\"\"\")!#>F#!\"(!#=!#5" }}} {EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#%?G" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 19 "A 4.4. Algoritmus. " }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "mFFT:=proc(a,x,omega,n, m) local A,B,C,b,c,i,j;\n" }{MPLTEXT 1 0 36 " if n=0 then return [a m od m] fi;\n" }{MPLTEXT 1 0 15 " b:=0; c:=0;\n" }{MPLTEXT 1 0 32 " fo r i from 0 to 2^(n-1)-1 do\n" }{MPLTEXT 1 0 30 " b:=b+coeff(a,x,2*i )*x^i;\n" }{MPLTEXT 1 0 32 " c:=c+coeff(a,x,2*i+1)*x^i;\n" } {MPLTEXT 1 0 7 " od;\n" }{MPLTEXT 1 0 37 " B:=mFFT(b,x,omega^2 mod m ,n-1,m);\n" }{MPLTEXT 1 0 37 " C:=mFFT(c,x,omega^2 mod m,n-1,m);\n" } {MPLTEXT 1 0 22 " A:=[0$j=0..2^n-1];\n" }{MPLTEXT 1 0 32 " for i fro m 0 to 2^(n-1)-1 do\n" }{MPLTEXT 1 0 43 " A[i+1]:=B[i+1]+omega&^i*C [i+1] mod m;\n" }{MPLTEXT 1 0 51 " A[i+1+2^(n-1)]:=B[i+1]-omega&^i* C[i+1] mod m;\n" }{MPLTEXT 1 0 10 " od; A;\n" }{MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6'I\"aG6\"I\"xGF%I&omegaGF%I\"nGF%I \"mGF%6)I\"AGF%I\"BGF%I\"CGF%I\"bGF%I\"cGF%I\"iGF%I\"jGF%F%F%C+@$/F(\" \"!O7#-I$modGF%6$F$F)>F.F5>F/F5?(F0F5\"\"\",&)\"\"#,&F(F>F>!\"\"F>F>FC I%trueG%*protectedGC$>F.,&F.F>*&-I&coeffGFE6%F$F&,$*&FAF>F0F>F>F>)F&F0 F>F>>F/,&F/F>*&-FK6%F$F&,&FNF>F>F>F>FOF>F>>F,-I%mFFTGF%6'F.F&-F96$*$)F 'FAF>F)FBF)>F--FX6'F/F&FZFBF)>F+7#-I\"$GFE6$F5/F1;F5,&)FAF(F>F>FC?(F0F 5F>F?FDC$>&F+6#,&F0F>F>F>-F96$,&&F,FhoF>*&-I#&^GF%6$F'F0F>&F-FhoF>F>F) >&F+6#,(F0F>F>F>F@F>-F96$,&F]pF>F^pFCF)F+F%F%F%" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 46 "debug(mFFT); mFFT(a,x,14,3,41); undebug(mFFT); " }}{PARA 11 "" 1 "" {XPPMATH 20 "I%mFFTG6\"" }}{PARA 9 "" 1 "" {TEXT 207 64 "\{--> enter mFFT, args = 5*x^6+x^5+3*x^3+x^2-4*x+1, x, 14, 3, \+ 41" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&\"\"\"F# I\"xG6\"F#" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&\"\"%!\"\"*&\"\"$\"\"\"I \"xG6\"F'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&\"\"\"F#I\"xG6\"F#" }} {PARA 11 "" 1 "" {XPPMATH 20 ",(\"\"%!\"\"*&\"\"$\"\"\"I\"xG6\"F'F'*$) F(\"\"#F'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 ",(\"\"\"F#I\"xG6\"F#*&\" \"&F#)F$\"\"$F#F#" }}{PARA 11 "" 1 "" {XPPMATH 20 ",(\"\"%!\"\"*&\"\"$ \"\"\"I\"xG6\"F'F'*$)F(\"\"#F'F'" }}{PARA 9 "" 1 "" {TEXT 207 47 "\{-- > enter mFFT, args = 1+x+5*x^3, x, 9, 2, 41" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" } }{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&\"\"\"F#*&\"\"&F#I\"xG6\"F#F#" }}{PARA 9 "" 1 "" {TEXT 207 39 "\{-- > enter mFFT, args = 1, x, 1, 1, 41" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 9 "" 1 "" {TEXT 207 39 "\{--> enter mFFT, args = 1, x, 1, 0, 41" }{TEXT 207 37 "\n<-- exit mFFT (now in mFFT) = [1]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "7#\"\"\"" }}{PARA 9 "" 1 "" {TEXT 207 39 "\{--> enter mFF T, args = 0, x, 1, 0, 41" }{TEXT 207 37 "\n<-- exit mFFT (now in mFFT) = [0]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "7#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$\"\"!F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 " 7$\"\"\"F#" }}{PARA 9 "" 1 "" {TEXT 207 38 "<-- exit mFFT (now in mFFT ) = [1, 1]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$\"\"\"F#" }}{PARA 9 "" 1 "" {TEXT 207 43 "\{--> enter mFFT, args = 1+5*x, x, 1, 1, 41" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"&" }}{PARA 9 "" 1 "" {TEXT 207 39 "\{--> enter mFFT, \+ args = 1, x, 1, 0, 41" }{TEXT 207 37 "\n<-- exit mFFT (now in mFFT) = \+ [1]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "7#\"\"\"" }}{PARA 9 "" 1 "" {TEXT 207 39 "\{--> enter mFFT, args = 5, x, 1, 0, 41" }{TEXT 207 37 " \n<-- exit mFFT (now in mFFT) = [5]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "7#\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$\"\"!F#" }}{PARA 11 "" 1 " " {XPPMATH 20 "\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$\"\"'!\"%" }}{PARA 9 "" 1 "" {TEXT 207 39 "<-- exit mFFT (now in mFFT) = [6, -4]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 " 7$\"\"'!\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"\"!F#F#F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"&" }} {PARA 11 "" 1 "" {XPPMATH 20 "!\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" \"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"\"(!\"%!\"&\"\"'" }}{PARA 9 " " 1 "" {TEXT 207 46 "<-- exit mFFT (now in mFFT) = [7, -4, -5, 6]\}" } }{PARA 11 "" 1 "" {XPPMATH 20 "7&\"\"(!\"%!\"&\"\"'" }}{PARA 9 "" 1 "" {TEXT 207 48 "\{--> enter mFFT, args = -4+3*x+x^2, x, 9, 2, 41" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&I\"xG6\"\"\"\"\" \"%!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"$" }}{PARA 9 "" 1 "" {TEXT 207 41 "\{--> enter mFFT, args = x-4, x, 1, 1, 41" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }} {PARA 11 "" 1 "" {XPPMATH 20 "!\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" \"\"" }}{PARA 9 "" 1 "" {TEXT 207 39 "\{--> enter mFFT, args = 4, x, 1 , 0, 41" }{TEXT 207 38 "\n<-- exit mFFT (now in mFFT) = [-4]\}" }} {PARA 11 "" 1 "" {XPPMATH 20 "7#!\"%" }}{PARA 9 "" 1 "" {TEXT 207 39 " \{--> enter mFFT, args = 1, x, 1, 0, 41" }{TEXT 207 37 "\n<-- exit mFF T (now in mFFT) = [1]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "7#\"\"\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "7$\"\"!F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$!\"$!\"&" }}{PARA 9 "" 1 "" {TEXT 207 40 "<-- exit mFFT (now in mFFT) = [-3, -5]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$!\"$!\" &" }}{PARA 9 "" 1 "" {TEXT 207 39 "\{--> enter mFFT, args = 3, x, 1, 1 , 41" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 9 "" 1 "" {TEXT 207 39 "\{--> ente r mFFT, args = 3, x, 1, 0, 41" }{TEXT 207 37 "\n<-- exit mFFT (now in \+ mFFT) = [3]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "7#\"\"$" }}{PARA 9 "" 1 "" {TEXT 207 39 "\{--> enter mFFT, args = 0, x, 1, 0, 41" }{TEXT 207 37 "\n<-- exit mFFT (now in mFFT) = [0]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "7#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$\"\"!F#" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$\"\"$F#" }}{PARA 9 "" 1 "" {TEXT 207 38 "<-- exit mFFT (now in mFFT) = [3, 3]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$\"\"$F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"\"!F#F# F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"*" }}{PARA 11 " " 1 "" {XPPMATH 20 "!#>" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"\"!\"\"*! \"'!#>" }}{PARA 9 "" 1 "" {TEXT 207 47 "<-- exit mFFT (now in mFFT) = \+ [0, 9, -6, -19]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"\"!\"\"*!\"'!#> " }}{PARA 11 "" 1 "" {XPPMATH 20 "7*\"\"!F#F#F#F#F#F#F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"(" }} {PARA 11 "" 1 "" {XPPMATH 20 "!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "! \"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\")" }}{PARA 11 "" 1 "" {XPPMATH 20 "!#=" }}{PARA 11 "" 1 "" {XPPMATH 20 "!#>" }}{PARA 11 "" 1 "" {XPPMATH 20 "!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "7*\"\"(!\"\"\"\" )!#>F#!\"(!#=!#5" }}{PARA 9 "" 1 "" {TEXT 207 69 "<-- exit mFFT (now a t top level) = [7, -1, 8, -19, 7, -7, -18, -10]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "7*\"\"(!\"\"\"\")!#>F#!\"(!#=!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%mFFTG6\"" }}}{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%# %?G" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 8 "E 4.7. P" }{TEXT 206 12 "\303\251lda." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "`mod`:=modp;" }}{PARA 11 "" 1 "" {XPPMATH 20 "I% modpG%*protectedG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "4^4 mo d 17; [4^i$i=0..3] mod 17;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "7&\"\"\"\"\"%\"#;\"#8" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "A:=Matrix(4,(i,j)->4^((i-1)*(j-1)) mod 17) ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "-I'MatrixG6$%*protectedGI(_syslibG6 \"6#/I$%idGF'\"*+,M^\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "B :=Matrix(4,(i,j)->4^(-((i-1)*(j-1))) mod 17);" }}{PARA 11 "" 1 "" {XPPMATH 20 "-I'MatrixG6$%*protectedGI(_syslibG6\"6#/I$%idGF'\"*c=N^\" " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "evalm(A&*B); map(x->x m od 17,%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "=6\"6$;\"\"\"\"\"%F%E\\[l16 $\"\"#\"\"$\"$*G6$F'F'\"$h$6$F'F&\"#M6$F*F'\"$U%6$F&F&F'6$F+F*F,6$F+F+ \"$9&6$F&F'F06$F'F+F,6$F+F'F,6$F+F&F06$F*F&F06$F&F*F06$F*F*F.6$F'F*F26 $F&F+F0" }}{PARA 11 "" 1 "" {XPPMATH 20 "=6\"6$;\"\"\"\"\"%F%E\\[l16$ \"\"#\"\"$\"\"!6$F'F'F'6$F'F&F,6$F*F'F,6$F&F&F'6$F+F*F,6$F+F+F'6$F&F'F ,6$F'F+F,6$F+F'F,6$F+F&F,6$F*F&F,6$F&F*F,6$F*F*F'6$F'F*F,6$F&F+F," }}} {EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#%?G" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 19 "A 4.5. Algoritmus. " }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "`mod`:=mods;" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%modsG%*protectedG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "mFFT_Multiply:=proc(a,b,x,omega,n,m) local A,B,c,C ,i;\n" }{MPLTEXT 1 0 27 " A:=mFFT(a,x,omega,n,m);\n" }{MPLTEXT 1 0 27 " B:=mFFT(b,x,omega,n,m);\n" }{MPLTEXT 1 0 9 " c:=0;\n" }{MPLTEXT 1 0 28 " for i from 0 to 2^n-1 do\n" }{MPLTEXT 1 0 35 " c:=c+A[i+ 1]*B[i+1]*x^i mod m;\n" }{MPLTEXT 1 0 7 " od;\n" }{MPLTEXT 1 0 27 " \+ C:=mFFT(c,x,omega,n,m);\n" }{MPLTEXT 1 0 9 " c:=0;\n" }{MPLTEXT 1 0 28 " for i from 0 to 2^n-1 do\n" }{MPLTEXT 1 0 32 " c:=c+C[i+1]/2^ n*x^i mod m;\n" }{MPLTEXT 1 0 10 " od; c;\n" }{MPLTEXT 1 0 4 "end;" } }{PARA 11 "" 1 "" {XPPMATH 20 "f*6(I\"aG6\"I\"bGF%I\"xGF%I&omegaGF%I\" nGF%I\"mGF%6'I\"AGF%I\"BGF%I\"cGF%I\"CGF%I\"iGF%F%F%C*>F,-I%mFFTGF%6'F $F'F(F)F*>F--F46'F&F'F(F)F*>F.\"\"!?(F0F:\"\"\",&)\"\"#F)FF.-I$modGF%6$,&F.F<*(&F,6#,&F0FF/-F46'F.F'F(F)F*F9?(F0F:FF.-FE6$,&F.F<*(&F/FJFF@FMF " 0 "" {MPLTEXT 1 0 39 "a:=3*x^3+x^2-4*x+1; b:=x^3+2*x^2+5*x-3;" }}{PARA 11 "" 1 "" {XPPMATH 20 ",**&\"\"$\"\"\")I\"xG6\"F$F%F%*$)F'\"\"#F%F%*&\"\"%F%F'F% !\"\"F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 ",**$)I\"xG6\"\"\"$\"\"\"F(* &\"\"#F()F%F*F(F(*&\"\"&F(F%F(F(F'!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 64 "debug(mFFT_Multiply); mFFT_Multiply(a,b,x,14,3,41); e xpand(a*b);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I.mFFT_MultiplyG6\"" }} {PARA 9 "" 1 "" {TEXT 207 80 "\{--> enter mFFT_Multiply, args = 3*x^3+ x^2-4*x+1, x^3+2*x^2+5*x-3, x, 14, 3, 41" }}{PARA 11 "" 1 "" {XPPMATH 20 "7*\"\"\"\"\"*!#>!#=\"\"$\"#;\"#>!\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "7*\"\"&F#\"\"!\"#9!\"(!\"'!#5\"#;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&\"\"&\"\"\"*&\"\"%F$I\"xG6\"F$F$" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&\"\"&\"\"\"*&\"\"%F$I\"xG6\"F$F$" }}{PARA 11 "" 1 "" {XPPMATH 20 ",(\"\"&\"\"\"*&\"\"%F$I\"xG6\"F$F$*&\"\"'F$)F'\"\"$F$!\" \"" }}{PARA 11 "" 1 "" {XPPMATH 20 ",*\"\"&\"\"\"*&\"\"%F$I\"xG6\"F$F$ *&\"\"'F$)F'\"\"$F$!\"\"*&\"#?F$)F'F&F$F$" }}{PARA 11 "" 1 "" {XPPMATH 20 ",,\"\"&\"\"\"*&\"\"%F$I\"xG6\"F$F$*&\"\"'F$)F'\"\"$F$!\" \"*&\"#?F$)F'F&F$F$*&\"#9F$)F'F#F$F-" }}{PARA 11 "" 1 "" {XPPMATH 20 " ,.\"\"&\"\"\"*&\"\"%F$I\"xG6\"F$F$*&\"\"'F$)F'\"\"$F$!\"\"*&\"#?F$)F'F &F$F$*&\"#9F$)F'F#F$F-*&\"#:F$)F'F*F$F$" }}{PARA 11 "" 1 "" {XPPMATH 20 ",0\"\"&\"\"\"*&\"\"%F$I\"xG6\"F$F$*&\"\"'F$)F'\"\"$F$!\"\"*&\"#?F$ )F'F&F$F$*&\"#9F$)F'F#F$F-*&\"#:F$)F'F*F$F$*&\"\"(F$)F'F8F$F-" }} {PARA 11 "" 1 "" {XPPMATH 20 "7*\"#<\"\"!!#<\"#:!#>!\"'!\"%\"#8" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "! \"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&\"\"$!\"\"*&F#\"\"\")I\"xG6\"\"\"#F&F&" }}{PARA 11 "" 1 "" {XPPMATH 20 ",(\"\"$!\"\"*&F#\"\"\")I\"xG6\"\"\"#F&F&*&\"\"(F&)F(F #F&F&" }}{PARA 11 "" 1 "" {XPPMATH 20 ",*\"\"$!\"\"*&F#\"\"\")I\"xG6\" \"\"#F&F&*&\"\"(F&)F(F#F&F&*&\"#8F&)F(\"\"%F&F&" }}{PARA 11 "" 1 "" {XPPMATH 20 ",,\"\"$!\"\"*&F#\"\"\")I\"xG6\"\"\"#F&F&*&\"\"(F&)F(F#F&F &*&\"#8F&)F(\"\"%F&F&*&\"#6F&)F(\"\"&F&F$" }}{PARA 11 "" 1 "" {XPPMATH 20 ",.\"\"$!\"\"*&F#\"\"\")I\"xG6\"\"\"#F&F&*&\"\"(F&)F(F#F&F &*&\"#8F&)F(\"\"%F&F&*&\"#6F&)F(\"\"&F&F$*&\"#?F&)F(\"\"'F&F&" }} {PARA 11 "" 1 "" {XPPMATH 20 ",0\"\"$!\"\"*&F#\"\"\")I\"xG6\"\"\"#F&F& *&\"\"(F&)F(F#F&F&*&\"#8F&)F(\"\"%F&F&*&\"#6F&)F(\"\"&F&F$*&\"#?F&)F( \"\"'F&F&*&\"# " 0 "" {MPLTEXT 1 0 27 "14&^8 mod 41; 14&^4 mod 41;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"\"" }}}{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#%?G" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 9 "E 4.10. P" }{TEXT 206 12 "\303\251lda." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "with(numth eory);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7QI&GIgcdG6\"I)bigomegaGF$I&cf racGF$I)cfracpolGF$I+cyclotomicGF$I)divisorsGF$I)factorEQGF$I*factorse tGF$I'fermatGF$I)imagunitGF$I&indexGF$I/integral_basisGF$I)invcfracGF$ I'invphiGF$I*issqrfreeGF$I'jacobiGF$I*kroneckerGF$I'lambdaGF$I)legendr eGF$I)mcombineGF$I)mersenneGF$I(migcdexGF$I*minkowskiGF$I(mipolysGF$I% mlogGF$I'mobiusGF$I&mrootGF$I&msqrtGF$I)nearestpGF$I*nthconverGF$I)nth denomGF$I)nthnumerGF$I'nthpowGF$I&orderG%*protectedGI)pdexpandGF$I$phi GF$I#piGF$I*pprimrootGF$I)primrootGF$I(quadresGF$I+rootsunityGF$I*safe primeGF$I&sigmaGF$I*sq2factorGF$I(sum2sqrGF$I$tauGF$I%thueGF$" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "2.^31/ln(2.^31)/phi(2^20);" }}{PARA 11 "" 1 "" {XPPMATH 20 "$\"+'**=i!>!\"(" }}}{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#%?G" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 9 " E 4.11. P" }{TEXT 206 12 "\303\251lda." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "15&^8 mod 41; 15&^20 mo d 41;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#=" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "evalf (3./Pi^2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "$\"+3bjRI!#5" }}}{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#%?G" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 9 "E 4.12. P" }{TEXT 206 12 "\303\251lda." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "a:='a';\n" }{MPLTEXT 1 0 71 "powcreate(a(n)=1,a(0)=1,a(1)=-2,a(2)=3,a(3)=0,a(4)=1 ,a(5)=-1,a(6)=2);\n" }{MPLTEXT 1 0 35 "tpsform(a,x,8); convert(%,polyn om);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I\"aG6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "+3I\"xG6\"\"\"\"\"\"!!\"#F%\"\"$\"\"#F%\"\"%!\"\"\"\"&F) \"\"'F%\"\"(-I\"OG%*protectedG6#F%\"\")" }}{PARA 11 "" 1 "" {XPPMATH 20 ",0\"\"\"F#*&\"\"#F#I\"xG6\"F#!\"\"*&\"\"$F#)F&F%F#F#*$)F&\"\"%F#F# *$)F&\"\"&F#F(*&F%F#)F&\"\"'F#F#*$)F&\"\"(F#F#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 73 "tpsform(a,x,1); convert(%,polynom); y:=powpoly( 1/%,x); two:=powpoly(2,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "+'I\"xG6\" \"\"\"\"\"!-I\"OG%*protectedG6#F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I(powparmG6\"6$I#nnGF%I#t1 GF%6#IaoCopyright~(c)~1990~by~the~University~of~Waterloo.~All~rights~r eserved.GF%E\\s#\"\"!\"\"\"I#_kGF%F,C$@%-I%typeG%*protectedG6$F$I(inte gerGF3C$>F'-%)procnameG6#F.@%30-I#opGF36$\"\"%-F?6#F9I%NULLGF3-I$hasGF 36$7#-I(indicesGF36#F>F.C%>F(-I%subsGF36$/F.F$F'>-F96#%%argsG-I%evalGF 36#F(OFVO.FSC$>FSFenFZ7%I(powpolyG6$F3/I+modulenameGF%I*powseriesG6$F3 I(_syslibGF%F-I\"xGF%F%F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I(pow parmG6\"6$I#nnGF%I#t1GF%6#IaoCopyright~(c)~1990~by~the~University~of~W aterloo.~All~rights~reserved.GF%E\\s#\"\"!\"\"#I#_kGF%F,C$@%-I%typeG%* protectedG6$F$I(integerGF3C$>F'-%)procnameG6#F.@%30-I#opGF36$\"\"%-F?6 #F9I%NULLGF3-I$hasGF36$7#-I(indicesGF36#F>F.C%>F(-I%subsGF36$/F.F$F'>- F96#%%argsG-I%evalGF36#F(OFVO.FSC$>FSFenFZ7%I(powpolyG6$F3/I+modulenam eGF%I*powseriesG6$F3I(_syslibGF%F-I\"xGF%F%F%F%" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 58 "multiply(y,subtract(two,multiply(y,a))); tpsfo rm(%,x,2);\n" }{MPLTEXT 1 0 36 "convert(%,polynom); y:=powpoly(%,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I(powparmG6\"6$I#nnGF%I#t1GF%6#Iao Copyright~(c)~1990~by~the~University~of~Waterloo.~All~rights~reserved. GF%E\\s\"I#_kGF%-I$sumG6$%*protectedGI(_syslibGF%6$*&-I\"yGF%6#,&F,\" \"\"I\"jGF%!\"\"F8-I)_powser2GF%6#F9F8/F9;\"\"!F,C$@%-I%typeGF06$F$I(i ntegerGF0C$>F'-%)procnameG6#F,@%30-I#opGF06$\"\"%-FP6#FJI%NULLGF0-I$ha sGF06$7#-I(indicesGF06#FOF,C%>F(-I%subsGF06$/F,F$F'>-FJ6#%%argsG-I%eva lGF06#F(OFaoO.F^oC$>F^oFfoFeo7%I)multiplyG6$F0/I+modulenameGF%I*powser iesGF/F5f*F#F&F)E\\s'F@F8F8\"\"#,&F9F8F8F:-F<6#FbpF,,&-I$twoGF%FKF8-I) _powser1GF%FKF:F9F;,&F9F8F8F8-F<6#FjpC$FB7%I)subtractGF[pFgpf*F#F&F)E \\s%F@F8F8!\"#F9-FipF=F,-F.6$*&-F5F=F8-I\"aGF%F6F8F>C$FB7%FjoF5FiqF%F% F%F%F%F%F%F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "+)I\"xG6\"\"\"\"\"\"! \"\"#F%-I\"OG%*protectedG6#F%F'" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&\" \"\"F#*&\"\"#F#I\"xG6\"F#F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I(pow parmG6\"6$I#nnGF%I#t1GF%6#IaoCopyright~(c)~1990~by~the~University~of~W aterloo.~All~rights~reserved.GF%E\\s$\"\"!\"\"\"F-\"\"#I#_kGF%F,C$@%-I %typeG%*protectedG6$F$I(integerGF4C$>F'-%)procnameG6#F/@%30-I#opGF46$ \"\"%-F@6#F:I%NULLGF4-I$hasGF46$7#-I(indicesGF46#F?F/C%>F(-I%subsGF46$ /F/F$F'>-F:6#%%argsG-I%evalGF46#F(OFWO.FTC$>FTFfnFen7%I(powpolyG6$F4/I +modulenameGF%I*powseriesG6$F4I(_syslibGF%,&F-F-*&F.F-I\"xGF%F-F-FcoF% F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "multiply(y,subtract (two,multiply(y,a))); tpsform(%,x,4);\n" }{MPLTEXT 1 0 36 "convert(%,p olynom); y:=powpoly(%,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I(powpa rmG6\"6$I#nnGF%I#t1GF%6#IaoCopyright~(c)~1990~by~the~University~of~Wat erloo.~All~rights~reserved.GF%E\\s\"I#_kGF%-I$sumG6$%*protectedGI(_sys libGF%6$*&-I\"yGF%6#,&F,\"\"\"I\"jGF%!\"\"F8-I)_powser4GF%6#F9F8/F9;\" \"!F,C$@%-I%typeGF06$F$I(integerGF0C$>F'-%)procnameG6#F,@%30-I#opGF06$ \"\"%-FP6#FJI%NULLGF0-I$hasGF06$7#-I(indicesGF06#FOF,C%>F(-I%subsGF06$ /F,F$F'>-FJ6#%%argsG-I%evalGF06#F(OFaoO.F^oC$>F^oFfoFeo7%I)multiplyG6$ F0/I+modulenameGF%I*powseriesGF/F5f*F#F&F)E\\s(F@F8F8F@\"\"#F8,&F9F8F8 F8-F<6#Fbp,&F9F8FapF8-F<6#FepF,,&-I$twoGF%FKF8-I)_powser3GF%FKF:F9F;C$ FB7%I)subtractGF[pFjpf*F#F&F)E\\s&F@F8F8F@FapF:F9-F\\qF=F,-F.6$*&-F5F= F8-I\"aGF%F6F8F>C$FB7%FjoF5FhqF%F%F%F%F%F%F%F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "+-I\"xG6\"\"\"\"\"\"!\"\"#F%F%F'!\"%\"\"$-I\"OG%*protecte dG6#F%\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 ",*\"\"\"F#*&\"\"#F#I\"xG6 \"F#F#*$)F&F%F#F#*&\"\"%F#)F&\"\"$F#!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I(powparmG6\"6$I#nnGF%I#t1GF%6#IaoCopyright~(c)~1990~ by~the~University~of~Waterloo.~All~rights~reserved.GF%E\\s&\"\"!\"\"\" F-\"\"#F.F-\"\"$!\"%I#_kGF%F,C$@%-I%typeG%*protectedG6$F$I(integerGF6C $>F'-%)procnameG6#F1@%30-I#opGF66$\"\"%-FB6#FF(-I%subsGF66$/F1F$F'>-F<6#%%argsG-I%evalGF66#F(OF YO.FVC$>FVFhnFgn7%I(powpolyG6$F6/I+modulenameGF%I*powseriesG6$F6I(_sys libGF%,*F-F-*&F.F-I\"xGF%F-F-*$)FeoF.F-F-*&FDF-)FeoF/F-!\"\"FeoF%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "multiply(y,subtract(two, multiply(y,a))); tpsform(%,x,8);\n" }{MPLTEXT 1 0 36 "convert(%,polyno m); y:=powpoly(%,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I(powparmG6 \"6$I#nnGF%I#t1GF%6#IaoCopyright~(c)~1990~by~the~University~of~Waterlo o.~All~rights~reserved.GF%E\\s\"I#_kGF%-I$sumG6$%*protectedGI(_syslibG F%6$*&-I\"yGF%6#,&F,\"\"\"I\"jGF%!\"\"F8-I)_powser6GF%6#F9F8/F9;\"\"!F ,C$@%-I%typeGF06$F$I(integerGF0C$>F'-%)procnameG6#F,@%30-I#opGF06$\"\" %-FP6#FJI%NULLGF0-I$hasGF06$7#-I(indicesGF06#FOF,C%>F(-I%subsGF06$/F,F $F'>-FJ6#%%argsG-I%evalGF06#F(OFaoO.F^oC$>F^oFfoFeo7%I)multiplyG6$F0/I +modulenameGF%I*powseriesGF/F5f*F#F&F)E\\s,F@F8F8F@\"\"#F@\"\"$F@FR!#7 ,&F9F8FbpF8-F<6#Fdp,&F9F8FRF8-F<6#Fgp,&F9F8FapF8-F<6#FjpF9F;F,,&-I$two GF%FKF8-I)_powser5GF%FKF:,&F9F8F8F8-F<6#FbqC$FB7%I)subtractGF[pF_qf*F# F&F)E\\s(F@F8F8F@FapF@FbpF@FR\"#7F9-FaqF=F,-F.6$*&-F5F=F8-I\"aGF%F6F8F >C$FB7%FjoF5FarF%F%F%F%F%F%F%F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "+5I \"xG6\"\"\"\"\"\"!\"\"#F%F%F'!\"%\"\"$!#7\"\"%!#8\"\"&\"\"*\"\"'\"#d\" \"(-I\"OG%*protectedG6#F%\"\")" }}{PARA 11 "" 1 "" {XPPMATH 20 ",2\"\" \"F#*&\"\"#F#I\"xG6\"F#F#*$)F&F%F#F#*&\"\"%F#)F&\"\"$F#!\"\"*&\"#7F#)F &F+F#F.*&\"#8F#)F&\"\"&F#F.*&\"\"*F#)F&\"\"'F#F#*&\"#dF#)F&\"\"(F#F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I(powparmG6\"6$I#nnGF%I#t1GF%6#Iao Copyright~(c)~1990~by~the~University~of~Waterloo.~All~rights~reserved. GF%E\\s*\"\"!\"\"\"F-\"\"#F.F-\"\"$!\"%\"\"&!#8\"\"%!#7\"\"(\"#d\"\"' \"\"*I#_kGF%F,C$@%-I%typeG%*protectedG6$F$I(integerGF>C$>F'-%)procname G6#F9@%30-I#opGF>6$F3-FJ6#FDI%NULLGF>-I$hasGF>6$7#-I(indicesGF>6#FIF9C %>F(-I%subsGF>6$/F9F$F'>-FD6#%%argsG-I%evalGF>6#F(OFjnO.FgnC$>FgnF_oF^ o7%I(powpolyG6$F>/I+modulenameGF%I*powseriesG6$F>I(_syslibGF%,2F-F-*&F .F-I\"xGF%F-F-*$)F\\pF.F-F-*&F3F-)F\\pF/F-!\"\"*&\"#7F-)F\\pF3F-Fap*& \"#8F-)F\\pF1F-Fap*&F8F-)F\\pF7F-F-*&F6F-)F\\pF5F-F-F\\pF%F%F%" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "multiply(y,a); tpsform(%,x,8 );" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I(powparmG6\"6$I#nnGF%I#t1GF%6 #IaoCopyright~(c)~1990~by~the~University~of~Waterloo.~All~rights~reser ved.GF%E\\s\"I#_kGF%-I$sumG6$%*protectedGI(_syslibGF%6$*&-I\"yGF%6#I\" jGF%\"\"\"-I\"aGF%6#,&F,F8F7!\"\"F8/F7;\"\"!F,C$@%-I%typeGF06$F$I(inte gerGF0C$>F'-%)procnameG6#F,@%30-I#opGF06$\"\"%-FP6#FJI%NULLGF0-I$hasGF 06$7#-I(indicesGF06#FOF,C%>F(-I%subsGF06$/F,F$F'>-FJ6#%%argsG-I%evalGF 06#F(OFaoO.F^oC$>F^oFfoFeo7%I)multiplyG6$F0/I+modulenameGF%I*powseries GF/F5F:F%F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "+'I\"xG6\"\"\"\"\"\"!-I \"OG%*protectedG6#F%\"\")" }}}{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" " %#%?G" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 19 "A 4.6. Algoritmus. " }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "FastNewtonInversion:=proc(a,x,n) local y,yy,k,two;\n" } {MPLTEXT 1 0 45 " tpsform(a,x,1); yy:=convert(1/%,polynom);\n" } {MPLTEXT 1 0 40 " y:=powpoly(yy,x); two:=powpoly(2,x);\n" }{MPLTEXT 1 0 17 " for k to n do\n" }{MPLTEXT 1 0 64 " multiply(y,subtract(t wo,multiply(y,a))); tpsform(%,x,2^k);\n" }{MPLTEXT 1 0 47 " yy:=con vert(%,polynom); y:=powpoly(yy,x);\n" }{MPLTEXT 1 0 11 " od; yy;\n" } {MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"aG6\"I\"x GF%I\"nGF%6&I\"yGF%I#yyGF%I\"kGF%I$twoGF%F%F%C(-_I*powseriesG6$%*prote ctedGI(_syslibGF%I(tpsformGF%6%F$F&\"\"\">F*-I(convertGF26$*$I\"%GF%! \"\"I(polynomGF2>F)-_F0I(powpolyGF%6$F*F&>F,-FA6$\"\"#F&?(F+F6F6F'I%tr ueGF2C&-_F0I)multiplyGF%6$F)-_F0I)subtractGF%6$F,-FL6$F)F$-F/6%FF*-F96$FF?F*F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "FastNewtonInversion(a,x,3);" }}{PARA 11 "" 1 "" {XPPMATH 20 ",2\"\"\" F#*&\"\"#F#I\"xG6\"F#F#*$)F&F%F#F#*&\"\"%F#)F&\"\"$F#!\"\"*&\"#7F#)F&F +F#F.*&\"#8F#)F&\"\"&F#F.*&\"\"*F#)F&\"\"'F#F#*&\"#dF#)F&\"\"(F#F#" }} }{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#%?G" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 9 "E 4.13. P" }{TEXT 206 12 "\303\251lda." }}{PARA 0 " " 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "G:=( 1-2*t*x+x^2)^(-1/2); series(G,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "*$) ,(\"\"\"F%*(\"\"#F%I\"tG6\"F%I\"xGF)F%!\"\"*$)F*F'F%F%#F%F'F+" }} {PARA 11 "" 1 "" {XPPMATH 20 "+1I\"xG6\"\"\"\"\"\"!I\"tGF$F%,&#F%\"\"# !\"\"*&#\"\"$F*F%)F'F*F%F%F*,&*&F-F%F'F%F+*&#\"\"&F*F%)F'F.F%F%F.,(#F. \"\")F%*&#\"#:\"\"%F%F/F%F+*&#\"#NF8F%)F'F " 0 "" {MPLTEXT 1 0 45 "P:=(1 -2*t*x+x^2)*y^2-1; PP:=diff(P,y); y0:=1;" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&*&,(\"\"\"F%*(\"\"#F%I\"tG6\"F%I\"xGF)F%!\"\"*$)F*F'F%F%F%)I\"yG F)F'F%F%F%F+" }}{PARA 11 "" 1 "" {XPPMATH 20 ",$*(\"\"#\"\"\",(F%F%*(F $F%I\"tG6\"F%I\"xGF)F%!\"\"*$)F*F$F%F%F%I\"yGF)F%F%" }}{PARA 11 "" 1 " " {XPPMATH 20 "\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "y1 :=series(y0-subs(y=y0,P)/subs(y=y0,PP),x,2);\n" }{MPLTEXT 1 0 24 "y1:= convert(y1,polynom);" }}{PARA 11 "" 1 "" {XPPMATH 20 "+)I\"xG6\"\"\"\" \"\"!I\"tGF$F%-I\"OG%*protectedG6#F%\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&\"\"\"F#*&I\"tG6\"F#I\"xGF&F#F#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "y2:=series(y1-subs(y=y1,P)/subs(y=y1,PP),x,4); \n" }{MPLTEXT 1 0 24 "y2:=convert(y2,polynom);" }}{PARA 11 "" 1 "" {XPPMATH 20 "+-I\"xG6\"\"\"\"\"\"!I\"tGF$F%,&#F%\"\"#!\"\"*&#\"\"$F*F% )F'F*F%F%F*,(*$)F'F.F%F%F'F+*(F)F%,&*&F.F%F/F%F%F%F+F%F'F%F%F.-I\"OG%* protectedG6#F%\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 ",*\"\"\"F#*&I\"tG 6\"F#I\"xGF&F#F#*&,&#F#\"\"#!\"\"*&#\"\"$F+F#)F%F+F#F#F#)F'F+F#F#*&,(* $)F%F/F#F#F%F,*(F*F#,&*&F/F#F0F#F#F#F,F#F%F#F#F#)F'F/F#F#" }}}{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#%?G" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 9 "E 4.15. P" }{TEXT 206 12 "\303\251lda." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "a:=4+x+2*x ^2+3*x^3;" }}{PARA 11 "" 1 "" {XPPMATH 20 ",*\"\"%\"\"\"I\"xG6\"F$*&\" \"#F$)F%F(F$F$*&\"\"$F$)F%F+F$F$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "P:=y^2-a; y0:=-2; y0:=2;" }}{PARA 11 "" 1 "" {XPPMATH 20 ",,* $)I\"yG6\"\"\"#\"\"\"F(\"\"%!\"\"I\"xGF&F**&F'F()F+F'F(F**&\"\"$F()F+F /F(F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "yy:=s eries(2-(4-a)/4,x,2); yy:=convert(yy,polynom);" }}{PARA 11 "" 1 "" {XPPMATH 20 "+)I\"xG6\"\"\"#\"\"!#\"\"\"\"\"%F(-I\"OG%*protectedG6#F(F %" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&\"\"#\"\"\"*&#F$\"\"%F$I\"xG6\"F$ F$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "yy:=series(yy-(yy^2-a )/2/yy,x,4); yy:=convert(yy,polynom);" }}{PARA 11 "" 1 "" {XPPMATH 20 "+-I\"xG6\"\"\"#\"\"!#\"\"\"\"\"%F(#\"#J\"#kF%#\"$`$\"$7&\"\"$-I\"OG%* protectedG6#F(F)" }}{PARA 11 "" 1 "" {XPPMATH 20 ",*\"\"#\"\"\"*&#F$\" \"%F$I\"xG6\"F$F$*&#\"#J\"#kF$)F(F#F$F$*&#\"$`$\"$7&F$)F(\"\"$F$F$" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "series(yy^2,x,4);" }}{PARA 11 "" 1 "" {XPPMATH 20 "+-I\"xG6\"\"\"%\"\"!\"\"\"F'\"\"#F(\"\"$F)-I\" OG%*protectedG6#F'F%" }}}{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#%?G " }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 19 "A 4.7. Algoritmus. " }} {PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "NewtonSolve:=proc(P,y,x,y0,n) local yy,k,PP;\n" }{MPLTEXT 1 0 26 " PP:=diff(P,y); yy:=y0;\n" }{MPLTEXT 1 0 17 " for k to n do\n" } {MPLTEXT 1 0 54 " yy:=series(yy-subs(y=yy,P)/subs(y=yy,PP),x,2^k); \n" }{MPLTEXT 1 0 30 " yy:=convert(yy,polynom);\n" }{MPLTEXT 1 0 11 " od; yy;\n" }{MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6'I\"PG6\"I\"yGF%I\"xGF%I#y0GF%I\"nGF%6%I#yyGF%I\"kGF%I#PPGF%F%F%C &>F--I%diffG%*protectedG6$F$F&>F+F(?(F,\"\"\"F6F)I%trueGF2C$>F+-I'seri esGF26%,&F+F6*&-I%subsGF26$/F&F+F$F6-F@6$FBF-!\"\"FEF')\"\"#F,>F+-I(co nvertGF26$F+I(polynomGF2F+F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "NewtonSolve(P,y,x,2,3);" }}{PARA 11 "" 1 "" {XPPMATH 20 ",2\" \"#\"\"\"*&#F$\"\"%F$I\"xG6\"F$F$*&#\"#J\"#kF$)F(F#F$F$*&#\"$`$\"$7&F$ )F(\"\"$F$F$*&#\"%tB\"&%Q;F$)F(F'F$!\"\"*&#\"&8&>\"'s58F$)F(\"\"&F$F:* &#\"'Hm8\"(_r4#F$)F(\"\"'F$F:*&#\"(,#z:\");sx;F$)F(\"\"(F$F$" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "series(%^2,x,8);" }}{PARA 11 "" 1 "" {XPPMATH 20 "+-I\"xG6\"\"\"%\"\"!\"\"\"F'\"\"#F(\"\"$F)-I\"OG %*protectedG6#F'\"\")" }}}{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#%? G" }}}}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 4 "5. K" }{TEXT 205 8 "\303\255" }{TEXT 205 9 "nai marad" }{TEXT 205 8 "\303\251" }{TEXT 205 3 "kol" }{TEXT 205 8 "\303\241" }{TEXT 205 1 "s" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 14 "6. Newton-iter" } {TEXT 205 8 "\303\241" }{TEXT 205 2 "ci" }{TEXT 205 8 "\303\263" } {TEXT 205 16 ", Hensel-felemel" }{TEXT 205 8 "\303\251" }{TEXT 205 1 " s" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 15 "7. Legnagyobb k" }{TEXT 205 8 "\303\266" }{TEXT 205 1 "z" }{TEXT 205 8 "\303\266" }{TEXT 205 6 "s oszt" }{TEXT 205 8 "\303\263" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 11 "8. Faktoriz" }{TEXT 205 8 "\303\241" }{TEXT 205 1 "l" }{TEXT 205 8 "\303\241" }{TEXT 205 1 "s" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 21 "9. Egyenletrendszerek" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 6 "10. Gr" }{TEXT 205 27 "\303\266bner-b\303\241zisok" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 10 "11. Racion" }{TEXT 205 8 "\303\241" }{TEXT 205 5 "lis t" }{TEXT 205 8 "\303\266" }{TEXT 205 3 "rtf" }{TEXT 205 8 "\303\274" }{TEXT 205 3 "ggv" }{TEXT 205 8 "\303\251" }{TEXT 205 11 "n yek integr" }{TEXT 205 8 "\303\241" }{TEXT 205 1 "l" }{TEXT 205 8 "\30 3\241" }{TEXT 205 2 "sa" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 23 "12. \+ A Risch-algoritmus." }}}{EXCHG {PARA 0 "> " 0 "" {XPPEDIT 19 1 "" "%#% ?G" }}}} {MARK "0 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }