FUNKCE

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

nsdr1[a_,b_]:=nsdr1[b,a,{1,0},{0,1}]/;a<b 
nsdr1[a_,b_]:=nsdr1[a,b,{1,0},{0,1}]/;a≥b 
nsdr1[a_,0,u_,v_]:={a,u}
nsdr1[a_,b_,u_,v_]:=nsdr1[b,Mod[a,b],v,u-v*Quotient[a,b]]

nsdr1qr[a_,b_]:=nsdr1qr[b,a,{1,0},{0,1}]/;a<b 
nsdr1qr[a_,b_]:=nsdr1qr[a,b,{1,0},{0,1}]/;a≥b 
nsdr1qr[a_,0,u_,v_]:={a,u}
nsdr1qr[a_,b_,u_,v_]:=With[{r=QuotientRemainder[a,b]},nsdr1qr[b,r[[2]],v,u-v*r[[1]]]]

nsd2[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 
]

nsdr2[x_,y_] := Module[ {r,a=x,b=y,u={1,0},v={0,1},w} ,
If[a<b,r=b;b=a;a=r];
While[b>0,w=v;v=u-v*Quotient[a,b];u=w;r=Mod[a,b]; a=b; b=r];
{a,u}
]

nsdr2qr[x_,y_] := Module[ {r,a=x,b=y,u={1,0},v={0,1},w} ,
If[a<b,r=b;b=a;a=r];
While[b>0,  r=QuotientRemainder[a,b]; w=v;v=u-v*r[[1]];u=w;a=b; b=r[[2]]];
{a,u}
]

MĚŘENÍ

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]

vysledkyr0=mereni[100,2000,100,10000,ExtendedGCD]

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

vysledkyr1=mereni[100,2000,100,100,nsdr1]

vysledkyr1qr=mereni[100,2000,100,100,nsdr1qr]

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

vysledkyr2=mereni[100,2000,100,100,nsdr2]

vysledkyr2qr=mereni[100,2000,100,100,nsdr2qr]

model=c1*x^n+c2

fit0=FindFit[vysledky0,model,{c1,c2,n},x]
fitr0=FindFit[vysledkyr0,model,{c1,c2,n},x]
fit1=FindFit[vysledky1,model,{c1,c2,n},x]
fitr1=FindFit[vysledkyr1,model,{c1,c2,n},x]
fitr1qr=FindFit[vysledkyr1qr,model,{c1,c2,n},x]
fit2=FindFit[vysledky2,model,{c1,c2,n},x]
fitr2=FindFit[vysledkyr2,model,{c1,c2,n},x]
fitr2qr=FindFit[vysledkyr2qr,model,{c1,c2,n},x]

Show[
ListPlot[vysledky0, PlotStyle->Red,AxesOrigin->{0,0}], Plot[model/.fit0 ,{x, 0,2000},PlotStyle->Red],
ListPlot[vysledkyr0, PlotStyle->Red,AxesOrigin->{0,0}], Plot[model/.fitr0 ,{x, 0,2000},PlotStyle->Red],
ListPlot[vysledky1, PlotStyle->Green,AxesOrigin->{0,0}], Plot[model/.fit1 ,{x, 0,2000},PlotStyle->Green],
ListPlot[vysledkyr1, PlotStyle->Green,AxesOrigin->{0,0}], Plot[model/.fitr1 ,{x, 0,2000},PlotStyle->Green],
ListPlot[vysledkyr1qr, PlotStyle->Green,AxesOrigin->{0,0}], Plot[model/.fitr1qr ,{x, 0,2000},PlotStyle->Green],
ListPlot[vysledky2, PlotStyle->Blue,AxesOrigin->{0,0}], Plot[model/.fit2 ,{x, 0,2000},PlotStyle->Blue],
ListPlot[vysledkyr2, PlotStyle->Blue,AxesOrigin->{0,0}], Plot[model/.fitr2 ,{x, 0,2000},PlotStyle->Blue],
ListPlot[vysledkyr2qr, PlotStyle->Blue,AxesOrigin->{0,0}], Plot[model/.fitr2qr ,{x, 0,2000},PlotStyle->Blue]
]

rozšířený Euklid: Mod+Quotient vs. QuotientRemainder

Show[
ListPlot[vysledkyr1, PlotStyle->Green,AxesOrigin->{0,0}], Plot[model/.fitr1 ,{x, 0,2000},PlotStyle->Green],
ListPlot[vysledkyr1qr, PlotStyle->Blue,AxesOrigin->{0,0}], Plot[model/.fitr1qr ,{x, 0,2000},PlotStyle->Blue]
]
Show[
ListPlot[vysledkyr2, PlotStyle->Green,AxesOrigin->{0,0}], Plot[model/.fitr2 ,{x, 0,2000},PlotStyle->Green],
ListPlot[vysledkyr2qr, PlotStyle->Blue,AxesOrigin->{0,0}], Plot[model/.fitr2qr ,{x, 0,2000},PlotStyle->Blue]
]

rozšířený Euklid: funkcionální vs. procedurální vs. vestavěné

Show[
ListPlot[vysledkyr0/100, PlotStyle->Red,AxesOrigin->{0,0}], Plot[(model/100)/.fit0 ,{x, 0,2000},PlotStyle->Red],
ListPlot[vysledkyr1, PlotStyle->Green,AxesOrigin->{0,0}], Plot[model/.fitr1 ,{x, 0,2000},PlotStyle->Green],
ListPlot[vysledkyr2qr, PlotStyle->Blue,AxesOrigin->{0,0}], Plot[model/.fitr2qr ,{x, 0,2000},PlotStyle->Blue]
]

Euklid: funkcionální vs. procedurální vs. vestavěné

Show[
ListPlot[vysledky0/100, 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]
]

Euklid: obyčejný vs. rozšířený

Show[
ListPlot[vysledky0, PlotStyle->Green,AxesOrigin->{0,0}], Plot[model/.fit0 ,{x, 0,2000},PlotStyle->Green],
ListPlot[vysledkyr0, PlotStyle->Blue,AxesOrigin->{0,0}], Plot[model/.fitr0 ,{x, 0,2000},PlotStyle->Blue]
]
Show[
ListPlot[vysledky1, PlotStyle->Green,AxesOrigin->{0,0}], Plot[model/.fit1 ,{x, 0,2000},PlotStyle->Green],
ListPlot[vysledkyr1, PlotStyle->Blue,AxesOrigin->{0,0}], Plot[model/.fitr1 ,{x, 0,2000},PlotStyle->Blue]
]
Show[
ListPlot[vysledky2, PlotStyle->Green,AxesOrigin->{0,0}], Plot[model/.fit1 ,{x, 0,2000},PlotStyle->Green],
ListPlot[vysledkyr2qr, PlotStyle->Blue,AxesOrigin->{0,0}], Plot[model/.fitr2qr ,{x, 0,2000},PlotStyle->Blue]
]