NSD v Z_p[x]: Eukleidův algoritmus

FUNKCE

euklid0[f_,g_,p_]:=PolynomialGCD[f,g,Modulus->p]

euklid1[f_,g_,p_]:=euklid1[g,f,p]/;Exponent[f,x]<Exponent[g,x]
euklid1[f_,0,p_]:=f
euklid1[f_,g_,p_]:=euklid1[g,PolynomialMod[f,g,Modulus->p],p]/;Exponent[f,x]≥Exponent[g,x]

euklid2[x_,y_,p_] := Module[ {r,f=x,g=y} ,
If[Exponent[f,x]<Exponent[g,x],r=g;g=f;f=r];
While[g=!=0, r= PolynomialMod[f,g,Modulus->p]; f=g; g=r];    (* POZOR!!! g≠0 nefunguje !!!*)
f 
]

RandomPoly[deg_,p_]:=Expand[FromDigits[Reverse[Table[RandomInteger[{0,p-1}],{i,0,deg}]],x]]

p=RandomPrime[1000]
f=RandomPoly[10,p]
g=RandomPoly[10,p]
euklid0[f,g,p]
euklid1[f,g,p]
euklid2[f,g,p]

MĚŘENÍ v závislosti na stupni

mereni[od_,do_,step_,opak_,p_,f_]:=
Table[
Module[{a,b},
a=RandomPoly[i,p];
b=RandomPoly[i,p];  
{i,Do[ f[a,b,p];,{opak}]//Timing//First}
],
{i,od,do,step}]

$IterationLimit=Infinity

vysledky0=mereni[100,2000,100,10,NextPrime[1000],euklid0]

vysledky1=mereni[100,500,20,1,NextPrime[1000],euklid1]

vysledky2=mereni[100,500,20,1,NextPrime[1000],euklid2]

model=c1*x^n+c2

fit0=FindFit[vysledky0,model,{c1,c2,n},x]
fit1=FindFit[vysledky1,model,{c1,c2,n},x]
fit2=FindFit[vysledky2,model,{c1,c2,n},x]

Show[ListPlot[vysledky0, PlotStyle->Red,AxesOrigin->{0,0}], Plot[model/.fit0 ,{x, 0,2000},PlotStyle->Red]]
Show[
ListPlot[vysledky1, PlotStyle->Green,AxesOrigin->{0,0}], Plot[model/.fit1 ,{x, 0,500},PlotStyle->Green],
ListPlot[vysledky2, PlotStyle->Blue,AxesOrigin->{0,0}], Plot[model/.fit2 ,{x, 0,500},PlotStyle->Blue]
]

MĚŘENÍ v závislosti na koeficientech (tj. na p)

merenikoef[od_,do_,step_,opak_,deg_,f_]:=
Table[
Module[{a,b,p},
p=NextPrime[2^i];
a=RandomPoly[deg,p];
b=RandomPoly[deg,p];  
{i,Do[ f[a,b,p];,{opak}]//Timing//First}
],
{i,od,do,step}]

vysledky0=merenikoef[50,1000,50,1,500,euklid0]

vysledky1=merenikoef[50,1000,50,1,200,euklid1]

vysledky2=merenikoef[50,1000,50,1,200,euklid2]

fit0=FindFit[vysledky0,model,{c1,c2,n},x]
fit1=FindFit[vysledky1,model,{c1,c2,n},x]
fit2=FindFit[vysledky2,model,{c1,c2,n},x]

Show[ListPlot[vysledky0, PlotStyle->Red,AxesOrigin->{0,0}], Plot[model/.fit0 ,{x, 0,1000},PlotStyle->Red]]
Show[
ListPlot[vysledky1, PlotStyle->Green,AxesOrigin->{0,0}], Plot[model/.fit1 ,{x, 0,1000},PlotStyle->Green],
ListPlot[vysledky2, PlotStyle->Blue,AxesOrigin->{0,0}], Plot[model/.fit2 ,{x, 0,1000},PlotStyle->Blue]
]

MĚŘENÍ 3D

mereni3D[od1_,do1_,step1_,od2_,do2_,step2_,opak_,f_]:=
Table[
Module[{a,b,c,p},
p=NextPrime[2^j];
a=RandomPoly[i,p];
b=RandomPoly[i,p];  
ClearSystemCache;
{i,j,Do[ c=f[a,b,p];,{opak}]//Timing//First}
],
{i,od1,do1,step1},{j,od2,do2,step2}]

vysledky0=Flatten[mereni3D[100,1000,100,50,500,50,1,euklid0],1]

vysledky1=Flatten[mereni3D[20,200,20,20,200,20,1,euklid1],1]

model3d=c1*x^n*y^m+c2

fit3d0=FindFit[vysledky0,model3d,{c1,c2,n,m},{x,y}]
fit3d1=FindFit[vysledky1,model3d,{c1,c2,n,m},{x,y}]

ListContourPlot[vysledky0]
ContourPlot[model3d/.fit3d0 ,{x, 0,1000},{y,0,1000}]

ListContourPlot[vysledky1]
ContourPlot[model3d/.fit3d1 ,{x, 0,1000},{y,0,1000}]