{VERSION 7 1 "Linux" "7.1" } {USTYLETAB {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 "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 "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 "Text Output" -1 2 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 "Bullet Item" -1 15 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 "Left Justified Maple Output" -1 12 1 {CSTYLE "" -1 -1 "" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Help" -1 10 1 {CSTYLE "" -1 -1 "" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }1 1 0 0 0 0 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 "Diagnostic" -1 9 1 {CSTYLE "" -1 -1 "Courier" 1 12 40 120 40 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 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 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 72 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 "Norm al" -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 }{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 Serif" 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 "Orde red List 4" -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 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 "Line Printed Output" -1 6 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 "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 "Wa rning" -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 "Error" -1 8 1 {CSTYLE "" -1 -1 "Courier" 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 "Fixed Width" -1 17 1 {CSTYLE "" -1 -1 "" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "He ading 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 List 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 } {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 "Courier" 1 12 200 0 200 1 2 1 2 2 1 2 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "Hyperlink" -1 17 "MS Serif" 1 12 0 128 128 1 2 2 1 2 2 2 0 0 0 1 }{PSTYLE "" -1 205 1 {CSTYLE "" -1 -1 "Times" 1 12 255 0 0 1 2 1 2 2 1 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT 203 66 "Sz\303\241m\303\255t\303 \263g\303\251pes sz\303\241melm\303\251let" }}}{EXCHG {PARA 19 "" 0 "" {TEXT 204 18 "J\303\241rai Antal" }}}{EXCHG {PARA 19 "" 0 "" {TEXT 204 68 "Ezek a programok csak szeml\303\251ltet\303\251sre szolg\303\2 41lnak" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 59 "1. A pr\303\255mek el oszl\303\241sa, szit\303\241l\303\241s" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 63 "2. Egyszer\305\261 faktoriz\303\241l\303\241si m\303\263 dszerek" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 64 "3. Egyszer\305\261 p r\303\255mtesztel\303\251si m\303\263dszerek" }}{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#%?G" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 18 "4. \+ Lucas-sorozatok" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 23 "5. Alkalmaz \303\241sok " }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 36 "6. Sz\303\241mo k \303\251s polinomok" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT 205 45 "7. Gyo rs Fourier-transzform\303\241ci\303\263" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 17 "7.1. Polinomszorz" }{TEXT 206 8 "\303\24 1" }{TEXT 206 26 "s gyors Fourier-transzform" }{TEXT 206 8 "\303\241" }{TEXT 206 2 "ci" }{TEXT 206 12 "\303\263val." }}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 29 "7.2. Gyors Fourier-transzform" }{TEXT 206 8 "\303\24 1" }{TEXT 206 2 "ci" }{TEXT 206 14 "\303\263 (FFT)" }{TEXT 206 1 "." } }{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 48 "# This procedure do the bit reversation of the\n" }{MPLTEXT 1 0 33 "# number x which is k bit long.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 34 "reverse:=proc(x,k) local xx,i,y;\n" }{MPLTEXT 1 0 16 " xx:=x; y:=0;\n" }{MPLTEXT 1 0 17 " for i to k do\n" }{MPLTEXT 1 0 26 " if type(xx,odd) then\n" } {MPLTEXT 1 0 31 " y:=2*y+1; xx:=(xx-1)/2;\n" }{MPLTEXT 1 0 10 " \+ else\n" }{MPLTEXT 1 0 25 " y:=2*y; xx:=xx/2;\n" }{MPLTEXT 1 0 9 " fi;\n" }{MPLTEXT 1 0 13 " od; y; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$I\"xG6\"I\"kGF%6%I#xxGF%I\"iGF%I\"yGF%F%F%C&>F(F$>F* \"\"!?(F)\"\"\"F0F&I%trueG%*protectedG@%-I%typeGF26$F(I$oddGF2C$>F*,&* &\"\"#F0F*F0F0F0F0>F(,&*&#F0FF*,$F;F0>F(,$F?F0F*F%F %F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 53 "# This procedure do the complex butterfly operation\n" }{MPLTEXT 1 0 46 "# between the two terms A[i] and A[j] of the\n" }{MPLTEXT 1 0 33 "# table A. The multiplier is w.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 38 "cbutterfly:=proc(A,i,j,w) local X,Y;\n" }{MPLTEXT 1 0 45 " X:=A[i]; Y:=A[j]*w; A[i]:=X+Y; A[j]:=X-Y;\n" } {MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I\"AG6\"I\"i GF%I\"jGF%I\"wGF%6$I\"XGF%I\"YGF%F%F%C&>F*&F$6#F&>F+*&&F$6#F'\"\"\"F(F 4>F.,&F*F4F+F4>F2,&F*F4F+!\"\"F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 36 "# This is a complex FFT procedu re.\n" }{MPLTEXT 1 0 62 "# It use the butterfly procedure to operate o n the vector A.\n" }{MPLTEXT 1 0 41 "# The number of rounds is k in th e FFT.\n" }{MPLTEXT 1 0 58 "# T is a table of the powers of primitive \+ root of unity.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 34 "cfft:=proc(A,T,k) local l,s,w,t;\n" }{MPLTEXT 1 0 24 "for l f rom 0 to k-1 do\n" }{MPLTEXT 1 0 28 " for s from 0 to 2^l-1 do\n" } {MPLTEXT 1 0 14 " w:=T[s];\n" }{MPLTEXT 1 0 36 " for t from 0 to 2^(k-l-1)-1 do\n" }{MPLTEXT 1 0 58 " cbutterfly(A,2^(k-l)*s+t,2^ (k-l)*s+t+2^(k-l-1),w);\n" }{MPLTEXT 1 0 9 " od;\n" }{MPLTEXT 1 0 7 " od;\n" }{MPLTEXT 1 0 8 "od; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"AG6\"I\"TGF%I\"kGF%6&I\"lGF%I\"sGF%I\"wGF%I\"tGF%F%F%?(F)\"\"! \"\"\",&F'F/F/!\"\"I%trueG%*protectedG?(F*F.F/,&)\"\"#F)F/F/F1F2C$>F+& F&6#F*?(F,F.F/,&)F7,(F'F/F)F1F/F1F/F/F1F2-I+cbutterflyGF%6&F$,&*&)F7,& F'F/F)F1F/F*F/F/F,F/,(FDF/F,F/F>F/F+F%F%F%" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 48 "# The pre procedure do the pr eparation for the\n" }{MPLTEXT 1 0 49 "# table T[0..2^k-1)] of powers \+ of the primitive\n" }{MPLTEXT 1 0 18 "# root of unity.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 28 "pre:=proc(T,k) local \+ i,xx;\n" }{MPLTEXT 1 0 19 "Digits:=2*Digits;\n" }{MPLTEXT 1 0 26 "for \+ i from 0 to 2^k-1 do\n" }{MPLTEXT 1 0 51 " T[i]:=evalf(exp(-2*Pi*I*re verse(i,k)/2^(k+1)));\n" }{MPLTEXT 1 0 5 "od;\n" }{MPLTEXT 1 0 19 "Dig its:=Digits/2;\n" }{MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$I\"TG6\"I\"kGF%6$I\"iGF%I#xxGF%F%F%C%>I'DigitsGF%,$*&\"\"#\"\" \"F,F0F0?(F(\"\"!F0,&)F/F&F0F0!\"\"I%trueG%*protectedG>&F$6#F(-I&evalf GF76#-I$expGF%6#,$**,$*&F/F0^#F0F0F0F0I#PiGF7F0-I(reverseGF%6$F(F&F0)F /,&F&F0F0F0F5F5>F,,$*&#F0F/F0F,F0F0F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "k:=5;\n" }{MPLTEXT 1 0 58 "A:=array(0..2^k-1); for i \+ from 0 to 2^k-1 do A[i]:=0 od:\n" }{MPLTEXT 1 0 35 "T:=array(0..2^(k-1 )-1); pre(T,k-1):" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"&" }}{PARA 11 " " 1 "" {XPPMATH 20 "=6\"6#;\"\"!\"#JE\\[l!" }}{PARA 11 "" 1 "" {XPPMATH 20 "=6\"6#;\"\"!\"#:E\\[l!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "A[1]:=1+I; cfft(A,T,5): print(A);" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&\"\"\"F#^#F#F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "I\"AG6 \"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "for i from 0 to 2^k-1 do\n" }{MPLTEXT 1 0 20 " j:=reverse(i,k);\n" }{MPLTEXT 1 0 49 " if \+ i " 0 "" {MPLTEXT 1 0 22 "cfft(A,T,5): print(A);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I\"AG6\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "fo r i from 0 to 2^k-1 do\n" }{MPLTEXT 1 0 20 " j:=reverse(i,k);\n" } {MPLTEXT 1 0 49 " if i " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 61 "# This procedure do the inverse complex bu tterfly operation\n" }{MPLTEXT 1 0 46 "# between the two terms A[i] an d A[j] of the\n" }{MPLTEXT 1 0 47 "# table A. The power of primitive u nity is w.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 41 "icbutterfly:=proc(A,i,j,w) local X,Y,e;\n" }{MPLTEXT 1 0 51 " X :=A[i]+A[j]; Y:=A[i]-A[j]; A[i]:=X; A[j]:=Y/w;\n" }{MPLTEXT 1 0 4 "end ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I\"AG6\"I\"iGF%I\"jGF%I\"wGF%6% I\"XGF%I\"YGF%I\"eGF%F%F%C&>F*,&&F$6#F&\"\"\"&F$6#F'F2>F+,&F0F2F3!\"\" >F0F*>F3*&F+F2F(F7F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 " #\n" }{MPLTEXT 1 0 47 "# This procedure is a complex IFFT procedure.\n " }{MPLTEXT 1 0 63 "# It use the ibutterfly procedure to operate on th e vector A.\n" }{MPLTEXT 1 0 63 "# The number of round in the FFT is k and T is a table of the\n" }{MPLTEXT 1 0 38 "# powers of primitive ro ot of unity.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 35 "icfft:=proc(A,T,k) local l,s,w,t;\n" }{MPLTEXT 1 0 30 "for l f rom k-1 to 0 by -1 do\n" }{MPLTEXT 1 0 28 " for s from 0 to 2^l-1 do \n" }{MPLTEXT 1 0 14 " w:=T[s];\n" }{MPLTEXT 1 0 36 " for t from 0 to 2^(k-l-1)-1 do\n" }{MPLTEXT 1 0 59 " icbutterfly(A,2^(k-l)* s+t,2^(k-l)*s+t+2^(k-l-1),w);\n" }{MPLTEXT 1 0 9 " od;\n" }{MPLTEXT 1 0 7 " od;\n" }{MPLTEXT 1 0 8 "od; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"AG6\"I\"TGF%I\"kGF%6&I\"lGF%I\"sGF%I\"wGF%I\"tGF%F %F%?(F),&F'\"\"\"F/!\"\"F0\"\"!I%trueG%*protectedG?(F*F1F/,&)\"\"#F)F/ F/F0F2C$>F+&F&6#F*?(F,F1F/,&)F7,(F'F/F)F0F/F0F/F/F0F2-I,icbutterflyGF% 6&F$,&*&)F7,&F'F/F)F0F/F*F/F/F,F/,(FDF/F,F/F>F/F+F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "for i from 0 to 2^k-1 do A[i]:=0 od :\n" }{MPLTEXT 1 0 33 "A[1]:=1+I; cfft(A,T,5): print(A);" }}{PARA 11 " " 1 "" {XPPMATH 20 ",&\"\"\"F#^#F#F#" }}{PARA 11 "" 1 "" {XPPMATH 20 " I\"AG6\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "icfft(A,T,k): p rint(A);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I\"AG6\"" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 10 "7.4. Szorz" }{TEXT 206 8 "\303\241" }{TEXT 206 18 "s komplex FFT-vel." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 47 "# The cdigmul procedure do the digit-by-digit\n" }{MPLTEXT 1 0 47 "# multiplication of the two numbers after the\n" }{MPLTEXT 1 0 50 "# cfft's. The resul t will be in the first table.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 31 "cdigmul:=proc(T,S,k) local i;\n" }{MPLTEXT 1 0 47 "for i from 0 to 2^k-1 do T[i]:=T[i]*S[i]; od;\n" }{MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"TG6\"I\"SGF%I\"kGF%6#I \"iGF%F%F%?(F)\"\"!\"\"\",&)\"\"#F'F,F,!\"\"I%trueG%*protectedG>&F$F(* &F4F,&F&F(F,F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "A:=ar ray(0..2^k-1); for i from 0 to 2^k -1 do A[i]:=0 od:\n" }{MPLTEXT 1 0 57 "B:=array(0..2^k-1); for i from 0 to 2^k -1 do B[i]:=0 od:" }} {PARA 11 "" 1 "" {XPPMATH 20 "=6\"6#;\"\"!\"#JE\\[l!" }}{PARA 11 "" 1 "" {XPPMATH 20 "=6\"6#;\"\"!\"#JE\\[l!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "A[0]:=1: A[1]:=1: A[2]:=1: print(A);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I\"AG6\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 70 "# This is the polynom multiplication, do multi plication or squaring.\n" }{MPLTEXT 1 0 67 "# A and B are the two poly nomials, the FFT and IFFT use k rounds.\n" }{MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 35 "polmulcfft:=proc(A,B,k) global T ;\n" }{MPLTEXT 1 0 13 "if A=B then\n" }{MPLTEXT 1 0 16 " cfft(A,T,k); \n" }{MPLTEXT 1 0 19 " cdigmul(A,A,k);\n" }{MPLTEXT 1 0 17 " icfft(A ,T,k);\n" }{MPLTEXT 1 0 6 "else\n" }{MPLTEXT 1 0 16 " cfft(A,T,k);\n" }{MPLTEXT 1 0 16 " cfft(B,T,k);\n" }{MPLTEXT 1 0 19 " cdigmul(A,B,k );\n" }{MPLTEXT 1 0 17 " icfft(A,T,k);\n" }{MPLTEXT 1 0 8 "fi; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"AG6\"I\"BGF%I\"kGF%F%F%F%@%/F$F &C%-I%cfftGF%6%F$I\"TGF%F'-I(cdigmulGF%6%F$F$F'-I&icfftGF%F-C&F+-F,6%F &F.F'-F0F#F2F%6#F.F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "pol mulcfft(A,A,k): print(map(x->x/2^k,A));" }}{PARA 11 "" 1 "" {XPPMATH 20 "=6\"6#;\"\"!\"#JE\\[lAF&,&$\"+%*********!#5\"\"\"*&$F&F&F-^#F-F-F- F-,&$\"+********>!\"*F-F.F-\"\"#,&$\"+********HF4F-F.F-\"\"$,&$\"+++++ ?F4F-F.F-\"\"&,&$\"+>Ee!3)!#?F-F.F-\"\"%,&$\"+++++5F4F-F.F-\"\"(,&$\"+ Izs^A!#>F-F.F-\"\"',&$\"+_]Lh5FJ!\"\"F.F-\"#5,&$\"+>;B>9FJFOF.F-\"#6,& $\"+AM4ViFJFOF.F-\"\"),&F/F-F.F-\"\"*,&$\"++++v=FJFOF.F-\"#:,&$\"+Q=E( y&FJF-F.F-\"#9,&$\"+Qih$*oFJF-F.F-\"#8,&$\"+:_#eK\"FJF-F.F-\"#7,&$\"+w M))eFFJFOF.F-\"#@,&$\"+Q<%>p\"FJF-F.F-\"#?,&$\"++++]iFJF-F.F-\"#B,&$\" +D-RgwFAF-F.F-\"#A,&$\"+G&=_%>FJF-F.F-\"#;F]p\"#,&$\"++ ++DJFJF-F.F-F',&$\"+)yG]I'FJFOF.FO\"#I,&$\"+7(*\\xxFJFOF.FO\"#H,&FboFO F.F-\"#G,&$\"+Q_;6**FAFOF.F-\"#E,&FRF-F.F-\"#F,&$\"++vd1p!#AFOF.F-\"#C FY\"#D,&FfnF-F.F-" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 52 "# The cfftpre procedure do the preparation for the\n" }{MPLTEXT 1 0 51 "# table for cfft, where x is the number, A is the\n " }{MPLTEXT 1 0 49 "# table, m the modulus, and k is the number of \n" }{MPLTEXT 1 0 53 "# rounds for the cfft, hence the table is 2^k long. \n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 36 "cfftp re:=proc(x,A,m,k) local i,xx;\n" }{MPLTEXT 1 0 8 "xx:=x;\n" }{MPLTEXT 1 0 53 "for i from 0 to 2^k-1 do A[i]:=irem(xx,m,'xx'); od;\n" } {MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I\"xG6\"I\"A GF%I\"mGF%I\"kGF%6$I\"iGF%I#xxGF%F%F%C$>F+F$?(F*\"\"!\"\"\",&)\"\"#F(F 0F0!\"\"I%trueG%*protectedG>&F&6#F*-I%iremGF66%F+F'.F+F%F%F%" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 44 "# The \+ cnorm procedure do the normalization\n" }{MPLTEXT 1 0 51 "# after the \+ icfft; A is the table, m the modulus,\n" }{MPLTEXT 1 0 47 "# and k is \+ the number of rounds for the cfft,\n" }{MPLTEXT 1 0 55 "# hence the ta ble is 2^k long. The fraction parts are\n" }{MPLTEXT 1 0 24 "# left in the table A.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 31 "cnorm:=proc(A,m,k) local i,x;\n" }{MPLTEXT 1 0 7 "x:=0;\n" } {MPLTEXT 1 0 32 "for i from 2^k-1 to 0 by -1 do\n" }{MPLTEXT 1 0 19 " \+ A[i]:=A[i]/2^k;\n" }{MPLTEXT 1 0 23 " x:=m*x+round(A[i]);\n" } {MPLTEXT 1 0 27 " A[i]:=A[i]-round(A[i]);\n" }{MPLTEXT 1 0 11 "od; x; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"AG6\"I\"mGF%I\"kGF%6$I\" iGF%I\"xGF%F%F%C%>F*\"\"!?(F),&)\"\"#F'\"\"\"F2!\"\"F3F-I%trueG%*prote ctedGC%>&F$6#F)*&F8F2F0F3>F*,&*&F&F2F*F2F2-I&roundG6$F5I(_syslibGF%6#F 8F2>F8,&F8F2F>F3F*F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 " #\n" }{MPLTEXT 1 0 70 "# This is the main procedure, do the multiplica tion or the squaring.\n" }{MPLTEXT 1 0 71 "# a and b are the two numbe rs, m is the modulus for the preparation. \n" }{MPLTEXT 1 0 42 "# The \+ complex FFT and IFFT use k rounds.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 38 "mulcfft:=proc(a,b,m,k) global A,B,T;\n" } {MPLTEXT 1 0 13 "if a=b then\n" }{MPLTEXT 1 0 21 " cfftpre(a,A,m,k); \n" }{MPLTEXT 1 0 16 " cfft(A,T,k);\n" }{MPLTEXT 1 0 19 " cdigmul(A, A,k);\n" }{MPLTEXT 1 0 17 " icfft(A,T,k);\n" }{MPLTEXT 1 0 17 " cnor m(A,m,k);\n" }{MPLTEXT 1 0 6 "else\n" }{MPLTEXT 1 0 21 " cfftpre(a,A, m,k);\n" }{MPLTEXT 1 0 16 " cfft(A,T,k);\n" }{MPLTEXT 1 0 21 " cfftp re(b,B,m,k);\n" }{MPLTEXT 1 0 16 " cfft(B,T,k);\n" }{MPLTEXT 1 0 19 " cdigmul(A,B,k);\n" }{MPLTEXT 1 0 17 " icfft(A,T,k);\n" }{MPLTEXT 1 0 17 " cnorm(A,m,k);\n" }{MPLTEXT 1 0 8 "fi; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I\"aG6\"I\"bGF%I\"mGF%I\"kGF%F%F%F%@%/F$F&C'-I(cfftp reGF%6&F$I\"AGF%F'F(-I%cfftGF%6%F/I\"TGF%F(-I(cdigmulGF%6%F/F/F(-I&icf ftGF%F2-I&cnormGF%6%F/F'F(C)F,F0-F-6&F&I\"BGF%F'F(-F16%F?F3F(-F56%F/F? F(F7F9F%6%F/F?F3F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "mulcf ft(123456789,987654321,20,5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"3p_j7 6jK>7" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "123456789*98765432 1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"3p_j76jK>7" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "print(A);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I\" AG6\"" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 8 "7.5. Val" }{TEXT 206 8 "\303\263" }{TEXT 206 6 "s FFT." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 53 "# The \+ CtoR procedure do the conversion from complex\n" }{MPLTEXT 1 0 42 "# r epresentation to real representation.\n" }{MPLTEXT 1 0 41 "# The resul t will be in the same table.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 32 "CtoR:=proc(A,T,k) local i,x,y;\n" }{MPLTEXT 1 0 27 "x:=Re(A[0]); y:=Im(A[0]);\n" }{MPLTEXT 1 0 26 "A[0]:=2*(x+y)+I*2 *(x-y);\n" }{MPLTEXT 1 0 27 "x:=Re(A[1]); y:=Im(A[1]);\n" }{MPLTEXT 1 0 18 "A[1]:=2*x-I*2*y;\n" }{MPLTEXT 1 0 41 "for i to k-1 do CtoRsteps( A,T,2^i); od;\n" }{MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"AG6\"I\"TGF%I\"kGF%6%I\"iGF%I\"xGF%I\"yGF%F%F%C)>F*-I#ReG%*pr otectedG6#&F$6#\"\"!>F+-I#ImGF0F1>F2,(*&\"\"#\"\"\"F*FF*-F/6#&F$6#F<>F+-F7FE>FF,&F:F<*&,$F? F " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 57 "# \+ The CtoRstep procedure do the conversion from complex\n" }{MPLTEXT 1 0 55 "# representation to real representation for one pair \n" } {MPLTEXT 1 0 25 "# ll, uu with weight w.\n" }{MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 62 "CtoRstep:=proc(ll,uu,w) local al ,be,ga,de,xi,et,a,b,x,y,u,v;\n" }{MPLTEXT 1 0 23 "xi:=Re(w); et:=Im(w) ;\n" }{MPLTEXT 1 0 25 "al:=Re(ll); be:=Im(ll);\n" }{MPLTEXT 1 0 25 "ga :=Re(uu); de:=Im(uu);\n" }{MPLTEXT 1 0 21 "x:=al+ga; y:=be-de;\n" } {MPLTEXT 1 0 21 "a:=al-ga; b:=be+de;\n" }{MPLTEXT 1 0 29 "u:=et*b-xi*a ; v:=xi*b+et*a;\n" }{MPLTEXT 1 0 27 "[x+v+I*(y+u),x-v+I*(u-y)]\n" } {MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I#llG6\"I#uu GF%I\"wGF%6.I#alGF%I#beGF%I#gaGF%I#deGF%I#xiGF%I#etGF%I\"aGF%I\"bGF%I \"xGF%I\"yGF%I\"uGF%I\"vGF%F%F%C/>F--I#ReG%*protectedG6#F'>F.-I#ImGF9F :>F)-F86#F$>F*-F=F@>F+-F86#F&>F,-F=FE>F1,&F)\"\"\"F+FJ>F2,&F*FJF,!\"\" >F/,&F)FJF+FM>F0,&F*FJF,FJ>F3,&*&F.FJF0FJFJ*&F-FJF/FJFM>F4,&*&F-FJF0FJ FJ*&F.FJF/FJFJ7$,(F1FJF4FJ*&^#FJFJ,&F2FJF3FJFJFJ,(F1FJF4FM*&FgnFJ,&F3F JF2FMFJFJF%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 58 "# The CtoRsteps procedure do the conversion from comp lex\n" }{MPLTEXT 1 0 57 "# representation to real representation for o ne series.\n" }{MPLTEXT 1 0 54 "# The index i is the lower index for t he first pair.\n" }{MPLTEXT 1 0 41 "# The result will be in the same t able.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 37 " CtoRsteps:=proc(A,T,i) local k,j,z;\n" }{MPLTEXT 1 0 17 "k:=i; j:=2*i- 1;\n" }{MPLTEXT 1 0 14 "while j>k do\n" }{MPLTEXT 1 0 72 " z:=CtoRste p(A[k],A[j],T[k]); A[k]:=z[1]; A[j]:=z[2]; k:=k+1; j:=j-1;\n" } {MPLTEXT 1 0 8 "od; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"AG6\" I\"TGF%I\"iGF%6%I\"kGF%I\"jGF%I\"zGF%F%F%C%>F)F'>F*,&*&\"\"#\"\"\"F'F2 F2F2!\"\"?(F%F2F2F%2F)F*C'>F+-I)CtoRstepGF%6%&F$6#F)&F$6#F*&F&F<>F;&F+ 6#F2>F=&F+6#F1>F),&F)F2F2F2>F*,&F*F2F2F3F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 50 "# The RtoC procedure do t he conversion from real\n" }{MPLTEXT 1 0 45 "# representation to compl ex representation.\n" }{MPLTEXT 1 0 41 "# The result will be in the sa me table.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 32 "RtoC:=proc(A,T,k) local i,x,y;\n" }{MPLTEXT 1 0 27 "x:=Re(A[0]); y :=Im(A[0]);\n" }{MPLTEXT 1 0 20 "A[0]:=x+y+I*(x-y);\n" }{MPLTEXT 1 0 27 "x:=Re(A[1]); y:=Im(A[1]);\n" }{MPLTEXT 1 0 18 "A[1]:=2*x-I*2*y;\n" }{MPLTEXT 1 0 41 "for i to k-1 do RtoCsteps(A,T,2^i); od;\n" } {MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"AG6\"I\"T GF%I\"kGF%6%I\"iGF%I\"xGF%I\"yGF%F%F%C)>F*-I#ReG%*protectedG6#&F$6#\" \"!>F+-I#ImGF0F1>F2,(F*\"\"\"F+F:*&^#F:F:,&F*F:F+!\"\"F:F:>F*-F/6#&F$6 #F:>F+-F7FA>FB,&*&\"\"#F:F*F:F:*&,$*&FIF:F?(F)F:F:,&F'F:F :F>I%trueGF0-I*RtoCstepsGF%6%F$F&)FIF)F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 69 "# The RtoCstep procedure do the conversion from real representation\n" }{MPLTEXT 1 0 65 "# to com plex representation for one pair ll, uu using weight w.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 62 "RtoCstep:=proc(ll,u u,w) local al,be,ga,de,xi,et,a,b,x,y,u,v;\n" }{MPLTEXT 1 0 23 "xi:=Re( w); et:=Im(w);\n" }{MPLTEXT 1 0 25 "al:=Re(ll); be:=Im(ll);\n" } {MPLTEXT 1 0 25 "ga:=Re(uu); de:=Im(uu);\n" }{MPLTEXT 1 0 21 "x:=al+ga ; y:=be-de;\n" }{MPLTEXT 1 0 21 "a:=al-ga; b:=be+de;\n" }{MPLTEXT 1 0 29 "u:=xi*a+et*b; v:=xi*b-et*a;\n" }{MPLTEXT 1 0 27 "[x-v+I*(u+y),x+v+ I*(u-y)]\n" }{MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6 %I#llG6\"I#uuGF%I\"wGF%6.I#alGF%I#beGF%I#gaGF%I#deGF%I#xiGF%I#etGF%I\" aGF%I\"bGF%I\"xGF%I\"yGF%I\"uGF%I\"vGF%F%F%C/>F--I#ReG%*protectedG6#F' >F.-I#ImGF9F:>F)-F86#F$>F*-F=F@>F+-F86#F&>F,-F=FE>F1,&F)\"\"\"F+FJ>F2, &F*FJF,!\"\">F/,&F)FJF+FM>F0,&F*FJF,FJ>F3,&*&F-FJF/FJFJ*&F.FJF0FJFJ>F4 ,&*&F-FJF0FJFJ*&F.FJF/FJFM7$,(F1FJF4FM*&^#FJFJ,&F2FJF3FJFJFJ,(F1FJF4FJ *&FgnFJ,&F3FJF2FMFJFJF%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 55 "# The RtoCsteps procedure do the conversion \+ from real\n" }{MPLTEXT 1 0 60 "# representation to complex representat ion for one series.\n" }{MPLTEXT 1 0 54 "# The index i is the lower in dex for the first pair.\n" }{MPLTEXT 1 0 41 "# The result will be in t he same table.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 37 "RtoCsteps:=proc(A,T,i) local k,j,z;\n" }{MPLTEXT 1 0 17 "k:=i ; j:=2*i-1;\n" }{MPLTEXT 1 0 14 "while j>k do\n" }{MPLTEXT 1 0 32 " z :=RtoCstep(A[k],A[j],T[k]);\n" }{MPLTEXT 1 0 47 " A[k]:=z[1]; A[j]:=z [2]; k:=k+1; j:=j-1; od;\n" }{MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"AG6\"I\"TGF%I\"iGF%6%I\"kGF%I\"jGF%I\"zGF%F%F%C%>F )F'>F*,&*&\"\"#\"\"\"F'F2F2F2!\"\"?(F%F2F2F%2F)F*C'>F+-I)RtoCstepGF%6% &F$6#F)&F$6#F*&F&F<>F;&F+6#F2>F=&F+6#F1>F),&F)F2F2F2>F*,&F*F2F2F3F%F%F %" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 10 "7.6. Szorz" }{TEXT 206 8 "\303\241" }{TEXT 206 33 "s komplex FFT-vel a gyakorlatban." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n " }{MPLTEXT 1 0 53 "# The srfftpre procedure do the preparation for th e\n" }{MPLTEXT 1 0 52 "# signed table for rfft; x is the number, A is \+ the\n" }{MPLTEXT 1 0 52 "# table, m the even positive modulus, and k i s the\n" }{MPLTEXT 1 0 63 "# number of rounds for the rfft, hence the \+ table is 2^k long.\n" }{MPLTEXT 1 0 44 "# All number is multipled by t he factor f.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 43 "srfftpre:=proc(x,A,m,k,f) local i,c,d,xx;\n" }{MPLTEXT 1 0 14 "xx:=x; c:=0;\n" }{MPLTEXT 1 0 26 "for i from 0 to 2^k-1 do\n" } {MPLTEXT 1 0 23 " d:=irem(xx,m,'xx');\n" }{MPLTEXT 1 0 57 " if d>=m/ 2 then d:=d-m+c; c:=1; else d:=d+c; c:=0; fi;\n" }{MPLTEXT 1 0 21 " A [i]:=evalf(d*f);\n" }{MPLTEXT 1 0 23 " d:=irem(xx,m,'xx');\n" } {MPLTEXT 1 0 57 " if d>=m/2 then d:=d-m+c; c:=1; else d:=d+c; c:=0; f i;\n" }{MPLTEXT 1 0 28 " A[i]:=A[i]+I*evalf(d*f);\n" }{MPLTEXT 1 0 8 "od; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6'I\"xG6\"I\"AGF%I\"mGF%I \"kGF%I\"fGF%6&I\"iGF%I\"cGF%I\"dGF%I#xxGF%F%F%C%>F.F$>F,\"\"!?(F+F2\" \"\",&)\"\"#F(F4F4!\"\"I%trueG%*protectedGC(>F--I%iremGF:6%F.F'.F.@%1, $*&#F4F7F4F'F4F4F-C$>F-,(F-F4F'F8F,F4>F,F4C$>F-,&F,F4F-F4F1>&F&6#F+-I& evalfGF:6#*&F-F4F)F4FFN,&FNF4*&^#F4F4FPF4F4F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 61 "# The rnorm p rocedure do the normalization after the irfft.\n" }{MPLTEXT 1 0 57 "# \+ A is the table, m the modulus, and k is the number of\n" }{MPLTEXT 1 0 53 "# rounds for the rfft, hence the table is 2^k long.\n" }{MPLTEXT 1 0 65 "# Before conversion, all entry in A multiplied by the factor \+ f.\n" }{MPLTEXT 1 0 47 "# The fraction parts are left in the table A. \n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 33 "rnorm :=proc(A,m,k,f) local i,x;\n" }{MPLTEXT 1 0 7 "x:=0;\n" }{MPLTEXT 1 0 32 "for i from 2^k-1 to 0 by -1 do\n" }{MPLTEXT 1 0 24 " A[i]:=evalf( A[i]*f);\n" }{MPLTEXT 1 0 27 " x:=m*x+round(Im(A[i]));\n" }{MPLTEXT 1 0 33 " A[i]:=A[i]-I*round(Im(A[i]));\n" }{MPLTEXT 1 0 27 " x:=m*x+ round(Re(A[i]));\n" }{MPLTEXT 1 0 31 " A[i]:=A[i]-round(Re(A[i]));\n" }{MPLTEXT 1 0 11 "od; x; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I \"AG6\"I\"mGF%I\"kGF%I\"fGF%6$I\"iGF%I\"xGF%F%F%C%>F+\"\"!?(F*,&)\"\"# F'\"\"\"F3!\"\"F4F.I%trueG%*protectedGC'>&F$6#F*-I&evalfGF66#*&F9F3F(F 3>F+,&*&F&F3F+F3F3-I&roundG6$F6I(_syslibGF%6#-I#ImGF66#F9F3>F9,&F9F3*& ,$^#F3F3F3FBF3F4>F+,&FAF3-FC6#-I#ReGF6FIF3>F9,&F9F3FQF4F+F%F%F%" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 47 "# The \+ rdigmul procedure do the digit-by-digit\n" }{MPLTEXT 1 0 47 "# multipl ication of the two numbers after the\n" }{MPLTEXT 1 0 50 "# rfft's. Th e result will be in the first table.\n" }{MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 31 "rdigmul:=proc(A,B,k) local i;\n" }{MPLTEXT 1 0 46 "A[0]:=Re(A[0])*Re(B[0])+I*Im(A[0])*Im(B[0]);\n" } {MPLTEXT 1 0 47 "for i from 1 to 2^k-1 do A[i]:=A[i]*B[i]; od;\n" } {MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"AG6\"I\"B GF%I\"kGF%6#I\"iGF%F%F%C$>&F$6#\"\"!,&*&-I#ReG%*protectedG6#F,\"\"\"-F 26#&F&F-F5F5*(^#F5F5-I#ImGF3F4F5-F&F$F(*&FEF5&F&F(F5F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 53 "# This is the main procedure, do the mu ltiplication\n" }{MPLTEXT 1 0 44 "# or the squaring using real FFT and IFFF.\n" }{MPLTEXT 1 0 53 "# a and b are the two numbers, m is the mo dulus for\n" }{MPLTEXT 1 0 51 "# the preparation. The FFT and IFFT use k rounds.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 61 "mulrfft:=proc(a,b,m,k) local f1,f2,r; global A,B,T;\n" } {MPLTEXT 1 0 21 "if type(k,odd) then\n" }{MPLTEXT 1 0 25 " f1:=2^(-(k +1)/2-HWS);\n" }{MPLTEXT 1 0 20 " f2:=2^(2*HWS-2);\n" }{MPLTEXT 1 0 6 "else\n" }{MPLTEXT 1 0 21 " f1:=2^(-k/2-HWS);\n" }{MPLTEXT 1 0 20 " f2:=2^(2*HWS-3);\n" }{MPLTEXT 1 0 5 "fi;\n" }{MPLTEXT 1 0 13 "if a=b then\n" }{MPLTEXT 1 0 35 " srfftpre(a,A,m,k,f1); print(A);\n" } {MPLTEXT 1 0 26 " cfft(A,T,k); print(A);\n" }{MPLTEXT 1 0 26 " CtoR( A,T,k); print(A);\n" }{MPLTEXT 1 0 29 " rdigmul(A,A,k); print(A);\n" }{MPLTEXT 1 0 26 " RtoC(A,T,k); print(A);\n" }{MPLTEXT 1 0 27 " icff t(A,T,k); print(A);\n" }{MPLTEXT 1 0 20 " rnorm(A,m,k,f2);\n" } {MPLTEXT 1 0 6 "else\n" }{MPLTEXT 1 0 25 " srfftpre(a,A,m,k,f1);\n" } {MPLTEXT 1 0 16 " cfft(A,T,k);\n" }{MPLTEXT 1 0 16 " CtoR(A,T,k);\n" }{MPLTEXT 1 0 25 " srfftpre(b,B,m,k,f1);\n" }{MPLTEXT 1 0 16 " cfft (B,T,k);\n" }{MPLTEXT 1 0 16 " CtoR(B,T,k);\n" }{MPLTEXT 1 0 19 " rd igmul(A,B,k);\n" }{MPLTEXT 1 0 16 " RtoC(A,T,k);\n" }{MPLTEXT 1 0 17 " icfft(A,T,k);\n" }{MPLTEXT 1 0 20 " rnorm(A,m,k,f2);\n" }{MPLTEXT 1 0 8 "fi; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I\"aG6\"I\"bGF%I \"mGF%I\"kGF%6%I#f1GF%I#f2GF%I\"rGF%F%F%C$@%-I%typeG%*protectedG6$F(I$ oddGF1C$>F*)\"\"#,(*&#\"\"\"F7F;F(F;!\"\"F:FF+)F7,&*&F7F;F =F;F;F7FF*)F7,&F9FF+)F7,&FAF;\"\"$F<@%/F$F&C/-I)srfftpreGF%6 'F$I\"AGF%F'F(F*-I&printGF16#FP-I%cfftGF%6%FPI\"TGF%F(FQ-I%CtoRGF%FVFQ -I(rdigmulGF%6%FPFPF(FQ-I%RtoCGF%FVFQ-I&icfftGF%FVFQ-I&rnormGF%6&FPF'F (F+C,FMFTFX-FN6'F&I\"BGF%F'F(F*-FU6%FaoFWF(-FYFco-Fen6%FPFaoF(FgnFinF[ oF%6%FPFaoFWF%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "HWS:=16; \+ k:=5;\n" }{MPLTEXT 1 0 42 "A:=array(0..2^k-1); B:=array(0..2^k-1); \n" }{MPLTEXT 1 0 29 "T:=array(0..2^k-1); pre(T,k):" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"&" }}{PARA 11 " " 1 "" {XPPMATH 20 "=6\"6#;\"\"!\"#JE\\[l!" }}{PARA 11 "" 1 "" {XPPMATH 20 "=6\"6#;\"\"!\"#JE\\[l!" }}{PARA 11 "" 1 "" {XPPMATH 20 "= 6\"6#;\"\"!\"#JE\\[l!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "mu lrfft(123456789,987654321,18,5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"3p _j76jK>7" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "123456789*98765 4321;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"3p_j76jK>7" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "print(A);" }}{PARA 11 "" 1 "" {XPPMATH 20 " I\"AG6\"" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 6 "7.7. P" }{TEXT 206 8 "\303\251" }{TEXT 206 4 "lda." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "HWS:=16; k:=15;\n" }{MPLTEXT 1 0 42 "A:=array(0..2^k-1); B:=array(0..2^k-1); \n" }{MPLTEXT 1 0 29 "T:=array(0..2^k-1); pre(T,k):" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#:" }}{PARA 11 "" 1 "" {XPPMATH 20 " =6\"6#;\"\"!\"&nF$E\\[l!" }}{PARA 11 "" 1 "" {XPPMATH 20 "=6\"6#;\"\"! \"&nF$E\\[l!" }}{PARA 11 "" 1 "" {XPPMATH 20 "=6\"6#;\"\"!\"&nF$E\\[l! " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "mulrfft(123456789,98765 4321,16,5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"3p_j76jK>7" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "123456789*987654321;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"3p_j76jK>7" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 10 "7.8. FFT v" }{TEXT 206 8 "\303\251" }{TEXT 206 18 "ges testek \+ felett." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 14 "7.9. Ferma t-sz" }{TEXT 206 8 "\303\241" }{TEXT 206 12 "m transzform" }{TEXT 206 8 "\303\241" }{TEXT 206 2 "ci" }{TEXT 206 8 "\303\263" }{TEXT 206 1 ". " }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 58 "# This procedure adds 1 to the number r epresented by the\n" }{MPLTEXT 1 0 57 "# bit vector b (used in reverse bit order) on length k.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 47 "incrementreverse:=proc(b,k) local i,c;\nc:=b;\n" } {MPLTEXT 1 0 66 "for i to k do if c[i]=0 then c[i]:=1; return c; else \+ c[i]:=0 fi;\n" }{MPLTEXT 1 0 11 "od; c; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$I\"bG6\"I\"kGF%6$I\"iGF%I\"cGF%F%F%C%>F)F$?(F(\"\"\"F -F&I%trueG%*protectedG@%/&F)6#F(\"\"!C$>F2F-OF)>F2F4F)F%F%F%" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 57 "# This procedure convert the bits in interval II of the\n" }{MPLTEXT 1 0 58 "# bit vector b. The bit b[1] represents the highest bit,\n" }{MPLTEXT 1 0 38 "# 2^(m-2+op(1,II)), usually 2^(m-1).\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 49 "convertreverse:=proc(b,m,II) l ocal i,lw; lw:=0;\n" }{MPLTEXT 1 0 36 "for i from op(1,II) to op(2,II) do\n" }{MPLTEXT 1 0 34 " lw:=lw+b[i]*2^(m-1-i+op(1,II))\n" }{MPLTEXT 1 0 12 "od; lw; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"bG6\"I\" mGF%I#IIGF%6$I\"iGF%I#lwGF%F%F%C%>F*\"\"!?(F)-I#opG%*protectedG6$\"\" \"F'F3-F06$\"\"#F'I%trueGF1>F*,&F*F3*&&F$6#F)F3)F6,*F&F3F3!\"\"F)F?F/F 3F3F3F*F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 60 "# This procedure do a Fermat FFT round modulo 2^(2^m) +1 on\n" }{MPLTEXT 1 0 59 "# array A having 2^n elements. The siccor s ize is 2^k and\n" }{MPLTEXT 1 0 66 "# the weights are get from the con version of bits in interval II\n" }{MPLTEXT 1 0 59 "# from a counter s tarting with zero and incremented after\n" }{MPLTEXT 1 0 28 "# each bu tterfly sequence.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" } {MPLTEXT 1 0 48 "ffftround:=proc(A,n,m,k,II) local i,j,x,y,w,b;\n" } {MPLTEXT 1 0 26 "j:=2^k; b:=[0$i=1..m+1];\n" }{MPLTEXT 1 0 16 "while j <2^n do\n" }{MPLTEXT 1 0 60 " w:=2^convertreverse(b,m,II); b:=increme ntreverse(b,m+1);\n" }{MPLTEXT 1 0 33 " for i from j-2^k while iF,)\"\"#F(>F07#-I\" $G%*protectedG6$\"\"!/F+;\"\"\",&F'F>F>F>?(F%F>F>F%2F,)F4F&C&>F/)F4-I/ convertreverseGF%6%F0F'F)>F0-I1incrementreverseGF%6$F0F??(F+,&F,F>F3! \"\"F>F%2F+F,C&>F-&F$6#F+>F.&F$6#,&F+F>F3F>>FS-I$modGF%6$,&F-F>*&F/F>F .F>F>,&)F4)F4F'F>F>F>>FV-Fen6$,&F-F>FhnFOFin>F,,&F,F>)F4,&F(F>F>F>F>F% F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 61 "# This procedure do a Fermat IFFT round modulo 2^(2^m)+1 on\n" } {MPLTEXT 1 0 59 "# array A having 2^n elements. The siccor size is 2^k and\n" }{MPLTEXT 1 0 66 "# the weights are get from the conversion of bits in interval II\n" }{MPLTEXT 1 0 59 "# from a counter starting wi th zero and incremented after\n" }{MPLTEXT 1 0 28 "# each butterfly se quence.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 49 "iffftround:=proc(A,n,m,k,II) local i,j,x,y,w,b;\n" }{MPLTEXT 1 0 26 "j:=2^k; b:=[0$i=1..m+1];\n" }{MPLTEXT 1 0 16 "while j<2^n do\n" } {MPLTEXT 1 0 60 " w:=2^convertreverse(b,m,II); b:=incrementreverse(b, m+1);\n" }{MPLTEXT 1 0 33 " for i from j-2^k while iF,)\"\"#F(>F07#-I\" $G%*protectedG6$\"\"!/F+;\"\"\",&F'F>F>F>?(F%F>F>F%2F,)F4F&C&>F/)F4-I/ convertreverseGF%6%F0F'F)>F0-I1incrementreverseGF%6$F0F??(F+,&F,F>F3! \"\"F>F%2F+F,C&>F-&F$6#F+>F.&F$6#,&F+F>F3F>>FS-I$modGF%6$,&F-F>F.F>,&) F4)F4F'F>F>F>>FV-Fen6$*&,&F-F>F.FOF>F/FOFhn>F,,&F,F>)F4,&F(F>F>F>F>F%F %F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 62 "# This is the digit-by-digit multiplication modulo 2^(2^m)+1\n" } {MPLTEXT 1 0 42 "# of arrays A and B having 2^n elements.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 33 "fdigmul:=proc(A,B, n,m) local i;\n" }{MPLTEXT 1 0 62 "for i from 0 to 2^n-1 do A[i]:=A[i] *B[i] mod (2^(2^m)+1) od;\n" }{MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I\"AG6\"I\"BGF%I\"nGF%I\"mGF%6#I\"iGF%F%F%?(F*\"\"! \"\"\",&)\"\"#F'F-F-!\"\"I%trueG%*protectedG>&F$F)-I$modGF%6$*&F5F-&F& F)F-,&)F0)F0F(F-F-F-F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 50 "# This procedure divides by 2^k modulo 2^(2^ m)+1\n" }{MPLTEXT 1 0 48 "# all elements of array A having 2^n element s.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 61 "fsh ift:=proc(A,n,m,k) local i,r;\nr:=1/2^k mod (2^(2^m)+1);\n" }{MPLTEXT 1 0 59 "for i from 0 to 2^n-1 do A[i]:=A[i]*r mod (2^(2^m)+1) od;\n" } {MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I\"AG6\"I\"n GF%I\"mGF%I\"kGF%6$I\"iGF%I\"rGF%F%F%C$>F+-I$modGF%6$*$)\"\"#F(!\"\",& )F3)F3F'\"\"\"F8F8?(F*\"\"!F8,&)F3F&F8F8F4I%trueG%*protectedG>&F$6#F*- F/6$*&F@F8F+F8F5F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "# \n" }{MPLTEXT 1 0 57 "# This procedure multiplies by sqrt(2) modulo 2^ (2^m)+1\n" }{MPLTEXT 1 0 81 "# all odd-indexed elements in the upper h alf of\n# array A having 2^n elements.\n" }{MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 50 "\nmulsqrt:=proc(A,n,m) local i,sqrttwo;\nsqrttwo:=" } {MPLTEXT 1 0 26 "2^(3*2^(m-2))-2^(2^(m-2));" }{MPLTEXT 1 0 2 "\n" } {MPLTEXT 1 0 39 "for i from 2^(n-1)+1 to 2^n-1 by 2 do\n" }{MPLTEXT 1 0 38 " A[i]:=A[i]*sqrttwo mod (2^(2^m)+1)\n" }{MPLTEXT 1 0 8 "od; end ;" }{MPLTEXT 1 0 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"AG6\"I\"n GF%I\"mGF%6$I\"iGF%I(sqrttwoGF%F%F%C$>F*,&)\"\"#,$*&\"\"$\"\"\")F/,&F' F3F/!\"\"F3F3F3)F/F4F6?(F),&)F/,&F&F3F3F6F3F3F3F/,&)F/F&F3F3F6I%trueG% *protectedG>&F$6#F)-I$modGF%6$*&FAF3F*F3,&)F/)F/F'F3F3F3F%F%F%" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 54 "# This procedure divides by sqrt(2) modulo 2^(2^m)+1\n" }{MPLTEXT 1 0 49 "# \+ all odd-indexed elements in the upper half of\n" }{MPLTEXT 1 0 32 "# a rray A having 2^n elements.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 " \n" }{MPLTEXT 1 0 40 "divsqrt:=proc(A,n,m) local i,sqrthalf;\n" } {MPLTEXT 1 0 58 "sqrthalf:=1/(2^(3*2^(m-2))-2^(2^(m-2))) mod (2^(2^m)+ 1);\n" }{MPLTEXT 1 0 39 "for i from 2^(n-1)+1 to 2^n-1 by 2 do\n" } {MPLTEXT 1 0 39 " A[i]:=A[i]*sqrthalf mod (2^(2^m)+1)\n" }{MPLTEXT 1 0 8 "od; end;" }{MPLTEXT 1 0 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6% I\"AG6\"I\"nGF%I\"mGF%6$I\"iGF%I)sqrthalfGF%F%F%C$>F*-I$modGF%6$*$,&) \"\"#,$*&\"\"$\"\"\")F3,&F'F7F3!\"\"F7F7F7)F3F8F:F:,&)F3)F3F'F7F7F7?(F ),&)F3,&F&F7F7F:F7F7F7F3,&)F3F&F7F7F:I%trueG%*protectedG>&F$6#F)-F.6$* &FHF7F*F7F " 0 "" {MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 49 "# This procedure do Fermat FFT modulo 2^(2^m)+1\n" } {MPLTEXT 1 0 36 "# for array A having 2^n elements.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 104 "\nffft:=proc(A,n,m) local i;\nfor i from 0 \+ to n-2 do ffftround(A,n,m,n-1-i,1..i) od;\nif m>=n-1 then\n " } {MPLTEXT 1 0 25 "ffftround(A,n,m,0,1..n-1)" }{MPLTEXT 1 0 26 "\nelse\n mulsqrt(A,n,m); " }{MPLTEXT 1 0 25 "ffftround(A,n,m,0,1..n-2)" } {MPLTEXT 1 0 10 "\nfi; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"AG 6\"I\"nGF%I\"mGF%6#I\"iGF%F%F%C$?(F)\"\"!\"\"\",&F&F-\"\"#!\"\"I%trueG %*protectedG-I*ffftroundGF%6'F$F&F',(F&F-F-F0F)F0;F-F)@%1,&F&F-F-F0F'- F46'F$F&F'F,;F-F:C$-I(mulsqrtGF%F#-F46'F$F&F'F,;F-F.F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 50 "# This proced ure do Fermat IFFT modulo 2^(2^m)+1\n" }{MPLTEXT 1 0 36 "# for array A having 2^n elements.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" } {MPLTEXT 1 0 29 "iffft:=proc(A,n,m) local i;\n" }{MPLTEXT 1 0 16 "if m >=n-1 then\n" }{MPLTEXT 1 0 30 " iffftround(A,n,m,0,1..n-1)\n" } {MPLTEXT 1 0 6 "else\n" }{MPLTEXT 1 0 46 " iffftround(A,n,m,0,1..n-2) ; divsqrt(A,n,m)\n" }{MPLTEXT 1 0 5 "fi;\n" }{MPLTEXT 1 0 63 "for i fr om n-2 to 0 by -1 do iffftround(A,n,m,n-1-i,1..i) od;\n" }{MPLTEXT 1 0 4 "end;" }{MPLTEXT 1 0 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"A G6\"I\"nGF%I\"mGF%6#I\"iGF%F%F%C$@%1,&F&\"\"\"F.!\"\"F'-I+iffftroundGF %6'F$F&F'\"\"!;F.F-C$-F16'F$F&F'F3;F.,&F&F.\"\"#F/-I(divsqrtGF%F#?(F)F 9F/F3I%trueG%*protectedG-F16'F$F&F',(F&F.F.F/F)F/;F.F)F%F%F%" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 65 "# This procedure do multiplication or squaring using Fermat FFT\n" }{MPLTEXT 1 0 60 "# and IFFT modulo 2^(2^m)+1 for array having 2^n elements.\n" }{MPLTEXT 1 0 43 "# 2^(m-1)-k bits is in one array element.\n" } {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 39 "ffftmul:=p roc(a,b,n,m) local i,c,A,B;\n" }{MPLTEXT 1 0 13 "if a=b then\n" } {MPLTEXT 1 0 53 " A:=Array(0..2^n-1,convert(a,base,2^(2^(m-1)-k)));\n " }{MPLTEXT 1 0 14 " ffft(A,n,m);" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 21 " fdigmul(A,A,n,m);\n" }{MPLTEXT 1 0 17 " iffft(A,n,m);\n" } {MPLTEXT 1 0 20 " fshift(A,n,m,n);\n" }{MPLTEXT 1 0 66 " c:=0; for i from 0 to 2^n-1 do c:=c+(2^(2^(m-1)-k))^i*A[i] od;\n" }{MPLTEXT 1 0 6 "else\n" }{MPLTEXT 1 0 53 " A:=Array(0..2^n-1,convert(a,base,2^(2^( m-1)-k)));\n" }{MPLTEXT 1 0 16 " ffft(A,n,m);\n" }{MPLTEXT 1 0 53 " \+ B:=Array(0..2^n-1,convert(b,base,2^(2^(m-1)-k)));\n" }{MPLTEXT 1 0 16 " ffft(B,n,m);\n" }{MPLTEXT 1 0 21 " fdigmul(A,B,n,m);\n" }{MPLTEXT 1 0 17 " iffft(A,n,m);\n" }{MPLTEXT 1 0 20 " fshift(A,n,m,n);\n" } {MPLTEXT 1 0 66 " c:=0; for i from 0 to 2^n-1 do c:=c+(2^(2^(m-1)-k)) ^i*A[i] od;\n" }{MPLTEXT 1 0 11 "fi; c; end;" }{MPLTEXT 1 0 0 "" }} {PARA 11 "" 1 "" {XPPMATH 20 "f*6&I\"aG6\"I\"bGF%I\"nGF%I\"mGF%6&I\"iG F%I\"cGF%I\"AGF%I\"BGF%F%F%C$@%/F$F&C)>F,-I&ArrayG%*protectedG6$;\"\"! ,&)\"\"#F'\"\"\"FF+F8?(F*F8FF+,&F+F<*&)FBF*F<&F,6#F*FF--F46$F7-F?6%F&FAFB-FH6%F-F'F(-FK6&F,F-F'F(FMFOFRFSF+F%F%F%" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "n:=6; m:=4; k:=4; ffftmul(12 3456789,987654321,n,m,k);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"'" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"3p_j76jK>7" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "123456789*987654321;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"3p_j76jK>7" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 9 "7. 10. Sch" }{TEXT 206 8 "\303\266" }{TEXT 206 16 "nhage-Strassen-f" } {TEXT 206 8 "\303\251" }{TEXT 206 13 "le gyorsszorz" }{TEXT 206 8 "\30 3\263" }{TEXT 206 12 " algoritmus." }}{PARA 0 "" 0 "" {TEXT 201 0 "" } }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 0 {PARA 4 "" 0 " " {TEXT 206 7 "7.11. P" }{TEXT 206 8 "\303\251" }{TEXT 206 4 "lda." }} {PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 33 "7.12. Ritka polinomok es ritka sz" }{TEXT 206 8 "\303\241" }{TEXT 206 4 "mok." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}} {SECT 1 {PARA 4 "" 0 "" {TEXT 206 14 "7.13. Feladat." }}{PARA 0 "" 0 " " {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}} {SECT 1 {PARA 4 "" 0 "" {TEXT 206 10 "7.14. Oszt" }{TEXT 206 8 "\303\2 41" }{TEXT 206 14 "s, polinomoszt" }{TEXT 206 8 "\303\241" }{TEXT 206 2 "s." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 16 "7.15. Poli nom ki" }{TEXT 206 8 "\303\251" }{TEXT 206 2 "rt" }{TEXT 206 8 "\303\2 51" }{TEXT 206 3 "kel" }{TEXT 206 8 "\303\251" }{TEXT 206 8 "se tetsz" }{TEXT 206 8 "\305\221" }{TEXT 206 15 "leges helyeken." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}} {SECT 1 {PARA 4 "" 0 "" {TEXT 206 14 "7.16. Interpol" }{TEXT 206 8 "\3 03\241" }{TEXT 206 2 "ci" }{TEXT 206 8 "\303\263" }{TEXT 206 1 "." }} {PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 14 "7.17. Feladat." }} {PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 14 "7.18. Feladat." }} {PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 14 "7.19. Feladat." }}} {PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 38 "8. Elliptikus f\303\274ggv\303\251nyek" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 59 "9. Sz\303\241mol\303 \241s elliptikus g\303\266rb\303\251ken" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 65 "10. Faktoriz\303\241l\30 3\241s elliptikus g\303\266rb\303\251kkel" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 55 "11. Pr\303\255mteszt elliptikus g\303\266rb\303\251kkel" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 37 "12. Polinomfaktoriz\303\241l \303\241s" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 16 "13. Az AKS-teszt" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 36 "14. A szita m\303\263dszerek alapjai" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{EXCHG {PARA 205 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 201 0 "" }}}{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 }