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

(* pocet iteraci *)
nsditerace[x_,y_] := Module[ {r,a=x,b=y,i=1} ,
If[a<b,r=b;b=a;a=r];
While[b>0,  r= Mod[a,b]; a=b; b=r;i++]; 
i
]

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

Table[{i,nsd[RandomInteger[2^i],RandomInteger[2^i]]},{i,10,2000,10}]

ListPlot[%]

Table[{i,nsditerace[RandomInteger[2^i],RandomInteger[2^i]]},{i,10,2000,10}]

ListPlot[%]

Table[{i,Log[10,nsdr[RandomInteger[2^i],RandomInteger[2^i]]]},{i,10,2000,10}];

ListPlot[%]