Sz\303\241m\303\255t\303\263g\303\251pes sz\303\241melm\303\251letJ\303\241rai AntalEzek a programok csak szeml\303\251ltet\303\251sre szolg\303\241lnak
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">1. A pr\303\255mek eloszl\303\241sa, szit\303\241l\303\241s</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">2. Egyszer\305\261 faktoriz\303\241l\303\241si m\303\263dszerek</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">3. Egyszer\305\261 pr\303\255mtesztel\303\251si m\303\263dszerek</Font></Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 1" layout="Heading 1">4. Lucas-sorozatok</Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">5. Alkalmaz\303\241sok </Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">6. Sz\303\241mok \303\251s polinomok</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">7. Gyors Fourier-transzform\303\241ci\303\263</Font></Text-field>restart;
<Text-field style="Heading 2" layout="Heading 2">7.1. Polinomszorz<Font encoding="UTF-8">\303\241</Font>s gyors Fourier-transzform<Font encoding="UTF-8">\303\241</Font>ci<Font encoding="UTF-8">\303\263val.</Font></Text-field>
<Text-field style="Heading 2" layout="Heading 2">7.2. Gyors Fourier-transzform<Font encoding="UTF-8">\303\241</Font>ci<Font encoding="UTF-8">\303\263 (FFT)</Font>.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">7.3. Inverz FFT.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">7.4. Szorz<Font encoding="UTF-8">\303\241</Font>s komplex FFT-vel.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">7.5. Val<Font encoding="UTF-8">\303\263</Font>s FFT.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">7.6. Szorz<Font encoding="UTF-8">\303\241</Font>s komplex FFT-vel a gyakorlatban.</Text-field>with(plots);L:=[[1972,130],[1982,400],[1985,800],[1985,1700],[1988,2670],[1991,16000],[1995,100000]];
LL:=map(x->[x[1],log[10.](x[2])],L);
L1:=[[1982,0.4],[1996,400]];
LL1:=map(x->[x[1],log[10.](x[2])],L1);
fti:=[TIMES,BOLD,25]; f1:=[TIMES,BOLD,15]; fa:=[TIMES,BOLD,15];display([plot(LL,1970..1998,color=blue,titlefont=fti,title='Supercomputers',
thickness=3),
plot(LL,1970..1998,color=blue,style=POINT,symbol=CIRCLE),
plot(LL1,1970..1998,color=red,thickness=3,axesfont=fa),
plot(LL1,1970..1998,color=red,style=POINT,symbol=CIRCLE),
textplot([1970,5.3,`log[10] `],align={ABOVE,LEFT},font=fa),
textplot([1970,4.9,`MFlops `],align={ABOVE,LEFT},font=fa),
textplot([LL1[1][1],LL1[1][2],`Z80 `],align={BELOW,LEFT},color=red,font=f1),textplot([LL1[2][1],LL1[2][2],`UltraSPARC I+ `],align={BELOW,LEFT},color=red,font=f1),textplot([LL[1][1],LL[1][2],`Cray-1 `],align={BELOW,RIGHT},color=blue,font=f1),
textplot([LL[2][1],LL[2][2],`Cray X-MP2 `],align={ABOVE,LEFT},color=blue,font=f1),
textplot([LL[3][1],LL[3][2],`Cray X-MP4 `],align={BELOW,RIGHT},color=blue,font=f1),
textplot([LL[4][1],LL[4][2],`Cray-2 `],align={LEFT},color=blue,font=f1),
textplot([LL[5][1],LL[5][2],`Cray Y-MP8 `],align={ABOVE,LEFT},color=blue,font=f1),
textplot([LL[6][1],LL[6][2],`Cray-3 `],align={ABOVE,LEFT},color=blue,font=f1),
textplot([LL[7][1],LL[7][2],`Cray-4 `],align={ABOVE,LEFT},color=blue,font=f1)]);b:=2.; WS:=32;
schmul:=[[5*WS,0.00003],[100*WS,0.007],[10382*WS,3.]];
classicmul:=[[WS,10.0/(4*10^7)],[2^5*WS,10.0*2^10/(4*10^7)]];
classicsqr:=[[WS,10.0/(4*10^7)],[2*WS,3*10.5/(4*10^7)],
[4*WS,10*10.5/(4*10^7)],[8*WS,34*10.5/(4*10^7)],
[16*WS,136*10.5/(4*10^7)],[2^5*WS,528*10.5/(4*10^7)]];
karamul:=[[2^2*WS,16.14/(4*10^6)],[2^3*WS,49.5/(4*10^6)],
[2^4*WS,16.74/(4*10^5)],[2^5*WS,54.25/(4*10^5)],[2^6*WS,17.17/(4*10^4)],
[2^7*WS,53.19/(4*10^4)],[2^8*WS,16.3/(4*10^3)],[2^9*WS,50.08/(4*10^3)],
[2^10*WS,15.3/400],[2^11*WS,46.78/400],[2^12*WS,14.25/40],
[2^13*WS,43.09/40],[2^14*WS,129.88/40],[2^15*WS,390.79/40]];
sqr:=[[2^2*WS,10.62/(4*10^6)],[2^3*WS,34.84/(4*10^6)],
[2^4*WS,12.44/(4*10^5)],[2^5*WS,43.02/(4*10^5)],[2^6*WS,14.32/(4*10^4)],
[2^7*WS,46.24/(4*10^4)],[2^8*WS,14.65/(4*10^3)],[2^9*WS,45.9/(4*10^3)],
[2^10*WS,14.37/400],[2^11*WS,44.24/400],[2^12*WS,13.59/40],
[2^13*WS,41.44/40],[2^14*WS,125.95/40],[2^15*WS,381.62/40]];
karasqr:=[[2^2*WS,10.89/(4*10^6)],[2^3*WS,34.45/(4*10^6)],
[2^4*WS,11.78/(4*10^5)],[2^5*WS,37.77/(4*10^5)],[2^6*WS,11.94/(4*10^4)],
[2^7*WS,36.49/(4*10^4)],[2^8*WS,10.61/(4*10^3)],[2^9*WS,32.39/(4*10^3)],
[2^10*WS,97.29/(4*10^3)],[2^11*WS,29.67/400],[2^12*WS,90.12/400],
[2^13*WS,26.61/(40*(32/33))],[2^14*WS,80.18/(40*(32/33))],
[2^15*WS,240.61/(40*(32/33))]];
fftmul:=[[7*WS*2,9.96/(4*10^4)],[7*WS*2^2,21.18/(4*10^4)],
[7*WS*2^3,45.44/(4*10^4)],[7*WS*2^4,9.79/(4*10^3)],
[7*WS*2^5,21.2/(4*10^3)],[7*WS*2^6,46.85/(4*10^3)],
[15*WS*2^5,51.53/(4*10^3)],[7*WS*2^7,10.42/400],
[15*WS*2^6,11.16/400],[7*WS*2^8,23.12/400],[15*WS*2^7,24.15/400],
[7*WS*2^9,50.06/400],[15*WS*2^8,51.54/400],[7*WS*2^10,10.96/40],
[15*WS*2^9,10.94/40],[15*WS*2^10,23.15/40],[15*WS*2^11,49.31/40]];
fftsqrold:=[[7*WS*2,73.51/(4*10^5)],[7*WS*2^2,15.62/(4*10^4)],
[7*WS*2^3,33.21/(4*10^4)],[7*WS*2^4,70.96/(4*10^4)],
[7*WS*2^5,15.45/(4*10^3)],[7*WS*2^6,33.06/(4*10^3)],
[15*WS*2^5,38.68/(4*10^3)],[7*WS*2^7,72.59/(4*10^3)],
[15*WS*2^6,82.1/(4*10^3)],[7*WS*2^8,16.42/400],[15*WS*2^7,18.05/400],
[7*WS*2^9,35.79/400],[15*WS*2^8,38.36/400],[7*WS*2^10,79.67/400],
[15*WS*2^9,81.51/400],[15*WS*2^10,17.42/40],[15*WS*2^11,37.43/40]];
fftsqr:=[[7*WS*2,70.43/(4*10^5)],[7*WS*2^2,14.92/(4*10^4)],
[7*WS*2^3,31.71/(4*10^4)],[7*WS*2^4,67.90/(4*10^4)],
[7*WS*2^5,14.60/(4*10^3)],[7*WS*2^6,31.32/(4*10^3)],
[15*WS*2^5,34.34/(4*10^3)],[7*WS*2^7,69.02/(4*10^3)],
[15*WS*2^6,73.35/(4*10^3)],[7*WS*2^8,15.64/400],[15*WS*2^7,16.24/400],
[7*WS*2^9,33.90/400],[15*WS*2^8,34.71/400],[7*WS*2^10,74.26/400],
[15*WS*2^9,73.64/400],[15*WS*2^10,16.03/40],[15*WS*2^11,33.53/40]];
rffftmulc:=[[22*2^5,14.80/(4*10^4)],[21*2^6,32.03/(4*10^4)],
[21*2^7,64.06/(4*10^4)],[20*2^8,14.34/(4*10^3)],
[20*2^9,30.21/(4*10^3)],[19*2^10,70.39/(4*10^3)],[19*2^11,16.81/400],
[18*2^12,35.45/400],[17*2^13,74.06/400],[17*2^14,15.59/40],
[16*2^15,32.32/40],[16*2^16,67.46/40]];
rffftmul2ss:=[[22*2^5,73.11/(4*10^5)],[21*2^6,14.35/(4*10^4)],
[21*2^7,28.78/(4*10^4)],[20*2^8,62.45/(4*10^4)],
[20*2^9,14.59/(4*10^3)],[19*2^10,35.65/(4*10^3)],[19*2^11,92.16/(4*10^3)],
[18*2^12,18.36/400],[17*2^13,42.46/400],[17*2^14,85.89/400],
[16*2^15,18.37/40],[16*2^16,37.84/40]];
rffftsqrc:=[[22*2^5,12.83/(4*10^4)],[21*2^6,26.39/(4*10^4)],
[21*2^7,54.81/(4*10^4)],[20*2^8,11.35/(4*10^3)],
[20*2^9,24.22/(4*10^3)],[19*2^10,54.75/(4*10^3)],[19*2^11,13.53/400],
[18*2^12,28.36/400],[17*2^13,60.39/400],[17*2^14,12.04/40],
[16*2^15,25.62/40],[16*2^16,52.58/40]];
rffftsqr2ss:=[[22*2^5,51.75/(4*10^5)],[21*2^6,10.44/(4*10^4)],
[21*2^7,19.83/(4*10^4)],[20*2^8,43.66/(4*10^4)],
[20*2^9,95.11/(4*10^4)],[19*2^10,25.53/(4*10^3)],[19*2^11,63.42/(4*10^3)],
[18*2^12,13.22/400],[17*2^13,28.36/400],[17*2^14,59.23/400],
[16*2^15,12.56/40],[16*2^16,25.85/40]];
lTpb:=proc(T) local x;
map(x->[log[b](x[1]),log[b](4*10^7*x[2]/x[1])],T);
end;
ppl:=proc(L)
pointplot([log[b](L[1]),log[b](24*3600/L[2])],
title=`Primality testing, log[2](test/day)-log[2](bit)`),
textplot([log[b](L[1]),log[b](24*3600/L[2]),L[3]],align={BELOW,LEFT})
end;
pplb:=proc(L)
pointplot([log[b](L[1]),log[b](24*3600/L[2])],
title=`Primality testing, log[2](test/day)-log[2](bit)`),
textplot([log[b](L[1]),log[b](24*3600/L[2]),L[3]],align={BELOW})
end;
pll:=proc(L) local x;
plot(map(x->[log[b](x[1]),log[b](24*3600/x[2])],L))
end;
ltpb:=proc(L) local x;
plot(map(x->[log[b](x[1]),log[b](24*3600/(f*x[2]*x[1]))],L));
end;display([plot(lTpb(schmul),style=POINT,title=`usqr, SuperSPARC, log[2](cycle/bit)-log[2](bit)`,color=magenta),
textplot([lTpb(schmul)[2][1],lTpb(schmul)[2][2],
`Schoenhage et al.`],align={ABOVE,LEFT}),
plot(lTpb(karamul),color=green),
plot(lTpb(karasqr),color=green),
textplot([lTpb(karamul)[10][1],lTpb(karamul)[10][2],
`Karatsuba`],align={ABOVE,LEFT}),
plot(lTpb(classicmul),color=blue),
plot(lTpb(classicsqr),color=blue),
textplot([lTpb(classicmul)[2][1],lTpb(classicmul)[2][2],
`Classic`],align={ABOVE,LEFT}),
plot(lTpb(fftmul),color=red),
plot(lTpb(fftsqr),color=red),
textplot([lTpb(fftmul)[1][1],lTpb(fftmul)[1][2],`Fermat`],
align={ABOVE,LEFT}),
plot(lTpb(rffftmul2ss),color=yellow),
plot(lTpb(rffftsqr2ss),color=yellow),
textplot([lTpb(rffftmul2ss)[12][1],lTpb(rffftmul2ss)[12][2],
`Float`],align={ABOVE,LEFT})]);f:=1.05*40/60;
T1:=[log[2](663777)+7650,6,`Twin, Amdahl 1200, 1989`];
T2:=[log[2](1706595)+11235,10,`Twin, Amdahl 1200, 1989`];
T3:=[log[2](697053813)+16352,212,`Twin, SuperSPARC 60 MHz, 1994`];
T4:=[log[2](697053813)+16352,2*24*3600,`Maple, SuperSPARC 60 MHz`];
T5:=[log[2](697053813)+16352,42.5*60,`LiDIA, MIPS RS4000`];
T6:=[log[2](697053813)+16352,3.5*3600,`LiDIA, SUN4 ELC`];
T7:=[log[2](242206083)+38880,7*60,`Twin, SuperSPARC 60MHz, 1995`];
T8:=[log[2](242206083)+38880,5*3600,`LiDIA, SPARCstation20`];
T:=[[WS*2^7,36.49/40000],[WS*2^8,10.61/4000],[19*2^10,25.53/(4*10^3)],
[19*2^11,63.42/(4*10^3)],[18*2^12,13.22/400],[17*2^13,28.36/400],
[17*2^14,59.23/400],[16*2^15,12.56/40],[16*2^16,25.85/40]];
M29:=[110503,0.03*110503,`Prime, NEC SX-2, 1988`];
M28:=[86243,5782,`Prime, CRAY-1, 1983`];
M31:=[216091,3*3600,`Prime, 1 CPU CRAY XMP, 1985`];
M33:=[859433,25924,`Prime, 1 CPU CRAY C916, 1994`];
P1:=[216100,33*60,`Prime, Amdahl 1200 E, 1990`];
# P:=[[128000,128000*0.2],[256000,256000*0.5],[512000,512000]];
display([ppl(T1),ppl(T2),ppl(T3),ppl(T4),ppl(T5),ppl(T6),ppl(T7),ppl(T8),
ltpb(T),ppl(M28),ppl(M29),ppl(M31),pplb(M33),ppl(P1)]);
<Text-field style="Heading 2" layout="Heading 2">7.7. P<Font encoding="UTF-8">\303\251</Font>lda.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">7.8. FFT v<Font encoding="UTF-8">\303\251</Font>ges testek felett.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">7.9. Fermat-sz<Font encoding="UTF-8">\303\241</Font>m transzform<Font encoding="UTF-8">\303\241</Font>ci<Font encoding="UTF-8">\303\263</Font>.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">7.10. Sch<Font encoding="UTF-8">\303\266</Font>nhage-Strassen-f<Font encoding="UTF-8">\303\251</Font>le gyorsszorz<Font encoding="UTF-8">\303\263</Font> algoritmus.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">7.11. P<Font encoding="UTF-8">\303\251</Font>lda.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">7.12. Ritka polinomok es ritka sz<Font encoding="UTF-8">\303\241</Font>mok.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">7.13. Feladat.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">7.14. Oszt<Font encoding="UTF-8">\303\241</Font>s, polinomoszt<Font encoding="UTF-8">\303\241</Font>s.</Text-field>#
# This procedure calculate the approximate reciprocal b of
# a given number a. The binary length of a must be 2^logn+1,
# where logn>2 is an integer. The result is [b,alpha,beta]
# where the parameters 0<alpha<1/2 and beta<=-2 are such that
# with the notation n=2^logn we have a*b=2^(2*n)-s with
# 0<s<=a*2^(alpha*n+beta).
#
apprec:=proc(a::posint,logn::posint) local n,b,ai,bi,L;
n:=2^logn;
if logn<=5 then
b:=floor(2^(2*n)/a);
if a*b=2^(2*n) then b:=b-1 fi;
RETURN([b,2/n,-2]);
fi;
ai:=iquo(a,2^(n/2));
L:=apprec(ai,logn-1);
bi:=L[1];
iquo(2^(3*n/2+1)*bi-bi*bi*a,2^n);
[%,L[2],L[3]]
end;apprec(256,3); apprec(257,3); apprec(300,3);
apprec(511,3); apprec(65536,4); apprec(65537,4);#
# This is a Maple demo program to show the procedure
# for division using the approximation of reciprocal
# based on Newton's method. Here, with the notation
# n=2^logn, c has at most 2n digit and a has at most
# n digit. logn must be an integer greater then 1.
#
division:=proc(c::posint,a::posint,logn::posint)
local n,k,l,as,bs,cs,qs,rs,alpha;
n:=2^logn; as:=a;
for k from 0 while as<2^n do as:=2*as od;
if c=0 then RETURN([0,0]) fi; cs:=floor(c/2);
for l from -1 while cs<2^(2*n-1) do cs:=2*cs od;
print(l); print(k);
if k<=0 or l<0 or k>l+1 then RETURN(`overflow`) fi;
cs:=iquo(cs,2^n); apprec(as,logn);
bs:=%[1]; alpha:=%%[2]; qs:=iquo(cs*bs,2^(n-k+l)); rs:=c-qs*a;
if k-l+alpha*n>1 then division(rs,a,logn); qs:=qs+%[1]; rs:=%%[2]; fi;
while rs>=a do qs:=qs+1; rs:=rs-a; od;
if qs>=2^n then RETURN(`overflow`) fi;
[qs,rs];
end;division(2^32,2^16,4);debug(division);division(2^32-10*2^16,2^16-1,4);%[1]*(2^16-1)+%[2]-(2^32-10*2^16);
<Text-field style="Heading 2" layout="Heading 2">7.15. Polinom ki<Font encoding="UTF-8">\303\251</Font>rt<Font encoding="UTF-8">\303\251</Font>kel<Font encoding="UTF-8">\303\251</Font>se tetsz<Font encoding="UTF-8">\305\221</Font>leges helyeken.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">7.16. Interpol<Font encoding="UTF-8">\303\241</Font>ci<Font encoding="UTF-8">\303\263</Font>.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">7.17. Feladat.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">7.18. Feladat.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">7.19. Feladat.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">7.20. Feladat: kontroll<Font encoding="UTF-8">\303\241</Font>lt euklid<Font encoding="UTF-8">\303\251</Font>szi lesz<Font encoding="UTF-8">\303\241</Font>ll<Font encoding="UTF-8">\303\241</Font>s.</Text-field># This function makes an upper or lower division step. The
# function updapes the incoming list [a,b,x,y,u,v], but the
# remainder is given back.
qstep:=proc(L,s) local q,r,LL;
if L[1]>L[2] then
q:=iquo(L[1],L[2]); r:=irem(L[1],L[2]);
if r>=s then
LL:=[r,L[2],L[3],L[4]+q*L[3],L[5],L[6]+q*L[5]];
else
LL:=[r,L[2],L[3],L[4]+(q-1)*L[3],L[5],L[6]+(q-1)*L[5]];
fi;
else
q:=iquo(L[2],L[1]); r:=irem(L[2],L[1]);
if r>=s then
LL:=[L[1],r,L[3]+q*L[4],L[4],L[5]+q*L[6],L[6]];
else
LL:=[L[1],r,L[3]+(q-1)*L[4],L[4],L[5]+(q-1)*L[6],L[6]];
fi;
fi;
LL;
end;# This is a slow version of ced. It works for arbitrary input.
# The matrix and the remainder is given back.
sced:=proc(a,b,s) local L;
L:=[a,b,1,0,0,1];
while L[1]>=s and L[2]>=s do
L:=qstep(L,s);
od;
L;
end;debug(sced);a:=floor(evalf(Pi*10.^8)); b:=floor(evalf(exp(1.)*10^8));
sced(a,b,1);3*(%[3]+%[4]),3*(%[5]+%[6]),%[3]*%[6]-%[4]*%[5];lB:=4; B:=2^lB; # wordsize and base of number systemcedmulQM:=proc(Q,M) local i,x,y,u,v,q;
x:=M[1]; y:=M[2]; u:=M[3]; v:=M[4];
for i from nops(Q) by -1 while i>0 do
q:=Q[i];
if q[1]=0 then
q:=q[2]; u:=u+q*x; v:=v+q*y;
else
q:=q[1]; x:=x+q*u; y:=y+q*v;
fi;
od;
[x,y,u,v];
end;cedmulMQ:=proc(M,Q) local i,x,y,u,v,q;
x:=M[1]; y:=M[2]; u:=M[3]; v:=M[4];
for i while i<=nops(Q) do
q:=Q[i];
if q[1]=0 then
q:=q[2]; x:=x+q*y; u:=u+q*v;
else
q:=q[1]; y:=y+q*x; v:=v+q*u;
fi;
od;
[x,y,u,v];
end;cedmulMM:=proc(M,MM) local x,y,u,v;
x:=M[1]*MM[1]+M[2]*MM[3];
y:=M[1]*MM[2]+M[2]*MM[4];
u:=M[3]*MM[1]+M[4]*MM[3];
v:=M[3]*MM[2]+M[4]*MM[4];
[x,y,u,v];
end;cedret:=proc(M,L) local x,y,u,v,q,MM,LL;
x:=M[1]; y:=M[2]; u:=M[3]; v:=M[4];
if L[4]=0 then
q:=L[5]; x:=x+q*y; u:=u+q*v;
else
q:=L[4];
y:=y+q*x; v:=v+q*u;
fi;
[L[1],L[2],x,y,u,v];
end;# Set the minimal positive integer l such that u,v<B^l
min_l:=proc(u,v) local l,l0,l1;
l0:=1; l1:=1;
while u>=B^l1 or v>=B^l1 do l0:=l1; l1:=2*l1; od;
l:=ceil((l0+l1)/2);
while l<l1 do
if u<B^l and v<B^l then l1:=l else l0:=l fi;
l:=ceil((l0+l1)/2);
od; l;
end;min_l(a,b);ced:=proc(a,b,n,w,e) local nn,np,ep,wp,aa,bb,ap,bp,app,bpp,f,s,L,M,MM,Q,t;
s:=w*B^e;
if n<=2 then return(sced(a,b,s)) fi;
nn:=n; aa:=a; bb:=b;
ep:=ceil(nn/4); np:=2*ep;
if nn-ep<e then ep:=nn-e; np:=2*ep fi;
f:=B^(nn-np);
ap:=floor(aa/f); bp:=floor(bb/f); app:=aa-ap*f; bpp:=bb-bp*f;
if e+ep=nn then wp:=w+1 else wp:=1;
if e>=ep and e>=nn-3*ep then
if ap*f+w*B^(e+ep)>B^nn or bp*f+w*B^(e+ep)>B^nn then wp:=2; fi;
fi;
fi;
if ap>=wp*B^ep and bp>=wp*B^ep then
L:=ced(ap,bp,np,wp,ep);
M:=[L[3],L[4],L[5],L[6]];
aa:=L[1]; bb:=L[2]; if aa<bb then aa:=aa+bb else bb:=bb+aa fi;
aa:=aa*f+M[4]*app-M[2]*bpp; bb:=bb*f-M[3]*app+M[1]*bpp;
else
M:=[1,0,0,1];
fi;
t:=M[1]*aa+M[2]*bb; t:=M[3]*aa+M[4]*bb; t:=M[1]*M[4]-M[2]*M[3]; # test
Q:=[];
while aa>=f*B^ep or bb>=f*B^ep do
L:=qstep([aa,bb,1,0,0,1],s);
aa:=L[1]; bb:=L[2];
if aa<s or bb<s then
L:=cedret(cedmulMQ(M,Q),L);
aa:=L[1]; bb:=L[2]; if aa<bb then aa:=aa+bb else bb:=bb+aa fi; # test
t:=L[3]*aa+L[4]*bb;t:=L[5]*aa+L[6]*bb;t:=L[3]*L[6]-L[4]*L[5]; # test
return(L);
fi;
Q:=[op(Q),[L[4],L[5]]];
od;
MM:=cedmulMQ(M,Q); #test
t:=MM[1]*aa+MM[2]*bb;t:=MM[3]*aa+MM[4]*bb;t:=MM[1]*MM[4]-MM[2]*MM[3]; # test
nn:=nn-ep;
if nn-ep<e then ep:=nn-e; np:=2*ep fi;
f:=B^(nn-np);
ap:=floor(aa/f); bp:=floor(bb/f); app:=aa-ap*f; bpp:=bb-bp*f;
if e+ep=nn then wp:=w+1 else wp:=1;
if e>=ep and e>=nn-3*ep then
if ap*f+w*B^(e+ep)>B^nn or bp*f+w*B^(e+ep)>B^nn then wp:=2; fi;
fi;
fi;
if ap>=wp*B^ep and bp>=wp*B^ep then
L:=ced(ap,bp,np,wp,ep);
MM:=[L[3],L[4],L[5],L[6]];
aa:=L[1]; bb:=L[2]; if aa<bb then aa:=aa+bb else bb:=bb+aa fi;
aa:=aa*f+MM[4]*app-MM[2]*bpp; bb:=bb*f-MM[3]*app+MM[1]*bpp;
else
MM:=[1,0,0,1];
fi;
MM:=cedmulQM(Q,MM); M:=cedmulMM(M,MM);
t:=M[1]*aa+M[2]*bb; t:=M[3]*aa+M[4]*bb; t:=M[1]*M[4]-M[2]*M[3]; # test
Q:=[];
while aa>=f*B^ep or bb>=f*B^ep do
L:=qstep([aa,bb,1,0,0,1],s);
aa:=L[1]; bb:=L[2];
if aa<s or bb<s then
L:=cedret(cedmulMQ(M,Q),L);
aa:=L[1]; bb:=L[2]; if aa<bb then aa:=aa+bb else bb:=bb+aa fi; # test
t:=L[3]*aa+L[4]*bb;t:=L[5]*aa+L[6]*bb;t:=L[3]*L[6]-L[4]*L[5]; # test
return(L);
fi;
Q:=[op(Q),[L[4],L[5]]];
od;
MM:=cedmulMQ(M,Q); #test
t:=MM[1]*aa+MM[2]*bb;t:=MM[3]*aa+MM[4]*bb;t:=MM[1]*MM[4]-MM[2]*MM[3]; # test
L:=ced(aa,bb,nn-ep,w,e);
MM:=[L[3],L[4],L[5],L[6]];
MM:=cedmulQM(Q,MM); M:=cedmulMM(M,MM);
aa:=L[1]; bb:=L[2]; if aa<bb then aa:=aa+bb else bb:=bb+aa fi; # test
t:=M[1]*aa+M[2]*bb;t:=M[3]*aa+M[4]*bb;t:=M[1]*M[4]-M[2]*M[3]; # test
[L[1],L[2],M[1],M[2],M[3],M[4]];
end;debug(ced);ced(a,b,min_l(a,b),1,0);3*(%[3]+%[4]),3*(%[5]+%[6]),%[3]*%[6]-%[4]*%[5];;;# m is the number of clock cycles used to multiple an n-word number
# by a one-word number
m:='m'; m1:='m1'; m:=proc(n) m1*n end; # m1:=10;m(2);# M is the number of clock cycles used to multiple two n-word numbers
M:='M'; M1:='M1';
M:=proc(n)
if n<=4 then n*n*M1
elif n<=512 then 2*3^log[2](n)*M1
else 15*n*log[2](n)*M1 fi
end;
# M1:=10;n:=2^13; evalf(log[2](32*n)); evalf(M(n)); evalf(log[2](M(n)/(32*n)));# a is the number of clock cycles used to calculate sum or difference
# of two n-word numbers
a:='a'; a1:='a1';
a:=proc(n) n*a1 end;
# a1:=6;a(1024);# r is the number of clock cycles used to calculate remainder
# by one-word quotient for two n-word numbers
r:='r'; r1:='r1';
r:=proc(n) n*r1 end;
# r1:=a1+m1;r(1024);# q is the number of clock cycles used to calculate a one-word quotient
q:='q';
# q:=60;# This the number of clock cycles used by ced to reduce a 2^n word
# number to the half length
C:=proc(n) 2*C(n-1)+8*q+4*m(2^n)+4*m(3*2^(n-2))+24*M(2^(n-2))
+16*a(2^(n-1))+58*c1 end;
C(0):=300;
C(1):=1000;
# c1:=20 # for call
C(2);C(3);C(4);C(5);C(6);C(7);C(8);C(9);C(10);C(11);C(12);C(13);C(14);C(15);C(16);C(17);interface(verboseproc=3);;
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">8. Elliptikus f\303\274ggv\303\251nyek</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">9. Sz\303\241mol\303\241s elliptikus g\303\266rb\303\251ken</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">10. Faktoriz\303\241l\303\241s elliptikus g\303\266rb\303\251kkel</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">11. Pr\303\255mteszt elliptikus g\303\266rb\303\251kkel</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">12. Polinomfaktoriz\303\241l\303\241s</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1">13. Az AKS-teszt</Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">14. A szita m\303\263dszerek alapjai</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">15. Sz\303\241mtest szita</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1">16. Vegyes probl<Font encoding="UTF-8">\303\251</Font>m<Font encoding="UTF-8">\303\241</Font>k</Text-field>LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn