NSD v Z: Eukleidův algoritmus vs. binární algoritmus

FUNKCE

euklid1[a_,b_]:=euklid1[b,a]/;a<b 
euklid1[a_,0]:=a
euklid1[a_,b_]:=euklid1[b,Mod[a,b]]

euklid2[x_,y_] := Module[ {r,a=x,b=y} ,
If[a<b,r=b;b=a;a=r];
While[b>0,  r= Mod[a,b]; a=b; b=r]; 
a 
]

euklid3[x_,y_] := Module[ {r,a=x,b=y} ,
While[b≠0,  r= a-b;If[r>0,a=b;b=r,b=-r]]; 
a 
]

binnsd[x_,y_] := Module[ {p,a=x,b=y,e=0} ,
While[Divisible[a,2] && Divisible[b,2],a=a/2;b=b/2;e++];
If[EvenQ[a],p=b;b=a;a=p];
While[b≠0, 
p=b;While[Divisible[p,2],p=p/2];
b=Abs[a-p];
a=Min[a,p];
];
2^e*a 
]

MĚŘENÍ v závislosti na n

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

$IterationLimit=Infinity

vysledky0=mereni[100,2000,100,10000,GCD]

vysledky1=mereni[100,2000,100,100,euklid1]

vysledky2=mereni[100,2000,100,100,euklid2]

vysledky3=mereni[100,2000,100,100,binnsd]

vysledky4=mereni[100,1000,100,100,euklid3]

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]
fit3=FindFit[vysledky3,model,{c1,c2,n},x]

Show[
ListPlot[Map[{#[[1]],#[[2]]/100}&,vysledky0], PlotStyle->Red,AxesOrigin->{0,0}], Plot[(model/100)/.fit0 ,{x, 0,2000},PlotStyle->Red],
ListPlot[vysledky1, PlotStyle->Green,AxesOrigin->{0,0}], Plot[model/.fit1 ,{x, 0,2000},PlotStyle->Green],
ListPlot[vysledky2, PlotStyle->Blue,AxesOrigin->{0,0}], Plot[model/.fit2 ,{x, 0,2000},PlotStyle->Blue],
ListPlot[vysledky3, PlotStyle->Black,AxesOrigin->{0,0}], Plot[model/.fit3 ,{x, 0,2000},PlotStyle->Black],
ListPlot[vysledky4, PlotStyle->Red,AxesOrigin->{0,0}]
]

Show[ListPlot[vysledky0, PlotStyle->Red,AxesOrigin->{0,0}], Plot[model/.fit0 ,{x, 0,2000},PlotStyle->Red]]

MĚŘENÍ v závislosti na m

merenim[n_,od_,do_,step_,opak_,f_]:=
Table[
Module[{a,b,c},
a=RandomInteger[2^n];
b=RandomInteger[2^i];  
ClearSystemCache;
{i,Do[ c=f[a,b];,{opak}]//Timing//First}
],
{i,od,do,step}]

vysledkym0=merenim[2000,100,2000,100,10000,GCD]

vysledkym1=merenim[2000,100,2000,100,100,euklid1]

vysledkym2=merenim[2000,100,2000,100,100,binnsd]

fitm0=FindFit[vysledkym0,model,{c1,c2,n},x]
fitm1=FindFit[vysledkym1,model,{c1,c2,n},x]
fitm2=FindFit[vysledkym2,model,{c1,c2,n},x]

Show[ListPlot[vysledkym0, PlotStyle->Red,AxesOrigin->{0,0}], Plot[model/.fitm0 ,{x, 0,2000},PlotStyle->Red]]
Show[ListPlot[vysledkym1, PlotStyle->Green,AxesOrigin->{0,0}], Plot[model/.fitm1 ,{x, 0,2000},PlotStyle->Green]]
Show[ListPlot[vysledkym2, PlotStyle->Black,AxesOrigin->{0,0}], Plot[model/.fitm2 ,{x, 0,2000},PlotStyle->Black]]

MĚŘENÍ 3D

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

vysledky3d0=Flatten[mereni3D[100,1000,100,100,1000,100,10000,GCD],1]

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

fit3d0=FindFit[vysledky3d0,model3d,{c1,c2,n,m},{x,y}]

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