{VERSION 3 0 "SGI MIPS UNIX" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 }{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 -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 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "with(MS):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 77 "When looking at the \{\\em Euler number s\}'' \\cite\{Abramowitz\}, generated by " }{XPPEDIT 18 0 "2/(exp(x)+ exp(-x));" "6#*&\"\"#\"\"\",&-%$expG6#%\"xGF%-F(6#,$F*!\"\"F%F." } {TEXT -1 22 ", the calculation of " }{XPPEDIT 18 0 "product(exp(x*ome ga[m]^i)+exp(-x*omega[m]^i),i = 0 .. m-1);" "6#-%(productG6$,&-%$expG6 #*&%\"xG\"\"\")&%&omegaG6#%\"mG%\"iGF,F,-F(6#,$*&F+F,)&F/6#F1F2F,!\"\" F,/F2;\"\"!,&F1F,\"\"\"F:" }{TEXT -1 0 "" }{TEXT -1 8 ", where " } {XPPEDIT 18 0 "omega[m];" "6#&%&omegaG6#%\"mG" }{TEXT -1 4 " is " } {XPPEDIT 18 0 "exp(2*Pi*I/m);" "6#-%$expG6#**\"\"#\"\"\"%#PiGF(%\"IGF( %\"mG!\"\"" }{TEXT -1 22 " is of interest. Set " }{XPPEDIT 18 0 "t(x) := exp(x)+exp(-x);" "6#>-%\"tG6#%\"xG,&-%$expG6#F'\"\"\"-F*6#,$F'!\" \"F," }{TEXT -1 5 " and " }{XPPEDIT 18 0 "s(x) := 2;" "6#>-%\"sG6#%\"x G\"\"#" }{TEXT -1 3 ". " }{TEXT -1 176 "This example will multisecti on by 4. An upper bound on the size of the linear recurrence relation is 16 from Lemma \\ref\{lem:d pow P\}. Also deg^d(t(x)) = 0, and he nce deg^d(" }{XPPEDIT 18 0 "product(t(x*omega[m]^i),i = 0 .. m-1);" "6 #-%(productG6$-%\"tG6#*&%\"xG\"\"\")&%&omegaG6#%\"mG%\"iGF+/F1;\"\"!,& F0F+\"\"\"!\"\"" }{TEXT -1 174 ") = 0. So polynomials of degree 32 n eeds to be calculated, and then linear algebra is used to determine th e result. So first calculate the Taylor series approximation for " } {XPPEDIT 18 0 "32!*t(x);" "6#*&-%*factorialG6#\"#K\"\"\"-%\"tG6#%\"xGF (" }{TEXT -1 12 ", call this " }{XPPEDIT 18 0 "T(x);" "6#-%\"TG6#%\"xG " }{TEXT -1 13 " (scaling by " }{XPPEDIT 18 0 "32!;" "6#-%*factorialG6 #\"#K" }{TEXT -1 69 " will mean that the calculation will avoid workin g over the rationals" }{TEXT -1 2 ")." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "t := exp(x)+exp(-x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"tG,&-%$expG6#%\"xG\"\"\"-F'6#,$F)!\"\"F*" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 43 "T := convert(taylor(t,x=0,33),polynom)*32!;" } }{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"TG,D\"E+++?V-OWLgqQnQnhi_\"\"\"*$ )%\"xG\"\"#\"\"\"\"E+++g@,=s;INpLp$38j#*$)F*\"\"%F,\"D+++!on\"os%3YuWu pv#>#*$)F*\"\"'F,\"B+++cAFU#G?[#[\"**=4t*$)F*\"\")F,\"A+++w0/!zk9!z%[7 _I\"*$)F*\"#5F,\"?++S1gb'QF6U4O-X\"*$)F*\"#7F,\"=++?:X8et2Pm)4\"*$)F* \"#9F,\":++gLi?o(yPhOg*$)F*\"#;F,\"8++k#>M:TdD:D*$)F*\"#=F,\"5++W$pP+! z>#)*$)F*\"#?F,\"3+!)3dKE5j@*$)F*\"#AF,\"0+S-LS?o%*$)F*\"#CF,\"-+?r&>[ )*$)F*\"#EF,\"+![;\\I\"*$)F*\"#GF,\"(!3E<*$)F*\"#IF,\"%%)>*$)F*\"#KF,F +" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 13 "Now multiply " }{XPPEDIT 18 0 "T(x);" "6#-%\"TG6#%\"xG" }{TEXT -1 4 " by " }{XPPEDIT 18 0 "T(-x); " "6#-%\"TG6#,$%\"xG!\"\"" }{TEXT -1 20 " and divide by 32!." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "T2 := convert(series(expand( T * subs(x=-x, T)),x,33),polynom)/32!;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#T2G,D\"F+++S'[?()o17uZtZL__5\"\"\"*$)%\"xG\"\"#\"\"\"F&*$)F* \"\"%F,\"E+++!)Go!HcNP\"f6f6T3N*$)F*\"\"'F,\"D+++%QCa]2)\\)y[X:)yn%*$) F*\"\")F,\"C+++cuQ]i)\\xi5'RMTL*$)F*\"#5F,\"B++g0NLQWMs/wT][\"*$)F*\" #7F,\"@++?fUPPA*e)oaE,]%*$)F*\"#9F,\">++S-8$4HQ8:!)Q!*)**$)F*\"#;F,\"= ++/b)[[IAD+)R[;*$)F*\"#=F,\";++ON\"46[2joZ:#*$)F*\"#?F,\"9+!)o1V101v*$)F*\"#CF,\"5+?z(\\qEOIU\"*$)F*\"#EF,\"2?( ywei9d()*$)F*\"#GF,\"0![#*=2TLY*$)F*\"#IF,\".;)yPII@*$)F*\"#KF,\"+#fM* *e)" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 18 "Now scale this by " } {XPPEDIT 18 0 "I;" "6#%\"IG" }{TEXT -1 53 ", so that the product will \+ give an approximation for " }{XPPEDIT 18 0 "T(x)*T(-x)*T(I*x)*T(-I*x)/ 32!;" "6#*,-%\"TG6#%\"xG\"\"\"-F%6#,$F'!\"\"F(-F%6#*&%\"IGF(F'F(F(-F%6 #,$*&F0F(F'F(F,F(-%*factorialG6#\"#KF," }{TEXT -1 1 "." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 69 "T3 := convert(series(expand(T2 * su bs(x=I*x, T2)),x,33),polynom)/32!;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6# >%#T3G,4\"F+++gX>)[vE['4R4R$45U\"\"\"*$)%\"xG\"\"%\"\"\"!F+++?:ti^A%\\ ljkjWO.9*$)F*\"\")F,\"E+++;%[R,0&**)f#)f#Q)G?\"*$)F*\"#7F,!B++!393WVP1 &Q\"=p:!e&*$)F*\"#;F,\"?++k+#4?I4:IpLd])*$)F*\"#?F,!<+?FqGW^nB#[:OY*$) F*\"#CF,\"9+?B.**RZC0Km6*$)F*\"#GF,!5?Z@&[zo!4=:*$)F*\"#KF,\"1#*4emU$f 7\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 63 "Now collect the coefficien ts of importance (the non-zero ones)." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "for i from 0 to 32 by 4 do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 " b[i/4] := coeff(T3,x,i)*i!/32!;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"bG6# \"\"!\"#;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"bG6#\"\"\"!$G\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"bG6#\"\"#\"&K%=" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"bG6#\"\"$!(3e,\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"bG6#\"\"%\")_Jjn" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"bG 6#\"\"&!+)oylG%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"bG6#\"\"'\"-sY 77]F" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"bG6#\"\"(!/o2cQ+f<" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"bG6#\"\")\"1#*4emU$f7\"" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 64 "Now use linear algebra to solve t he linear recurrence relation." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "recurrence/solve/linalg(b, f, x, 4);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/-%\"fG6#%\"xG,&-F%6#,&F'\"\"\"!\")F,\"%C5-F%6#,&F'F,! \"%F,!#[" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 75 "This could also have \+ be done by using the Maple function for this technique" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "bottom/ms/linalg/fft(t,f,x,4);" } }{PARA 11 "" 1 "" {XPPMATH 20 "6&/-%\"fG6#%\"xG,&-F%6#,&F'\"\"\"!\")F, \"%C5-F%6#,&F'F,!\"%F,!#[F%F'7+/-F%6#\"\"!\"#;/-F%6#F,F8/-F%6#\"\"#F8/ -F%6#\"\"$F8/-F%6#\"\"%!\$G\"/-F%6#\"\"&F8/-F%6#\"\"'F8/-F%6#\"\"(F8/-F %6#\"\")\"&K%=" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "Which is the sa me result." }}}}{MARK "1 0 14" 146 }{VIEWOPTS 1 1 0 1 1 1803 }