The Euclidean Algorithm

Math 5370c - Fall 2008

Helmut Knaust, Department of Mathematical Sciences, UTEP, El Paso TX 79968
hknaust@utep.edu
9/24/08

Using the engine behind the Euclidean Algorithm once: Since 
	162 = 5×31+7, 
we want to replace the pair {162,31} by the pair (31,7}

{a,b}={162,31}

a/b//N
IntegerPart[a/b]

{a,b}={b,a-IntegerPart[a/b] b}

Then we iterate this procdure until the smaller number equals 0:

a=162;b=31;{a,b}=Sort[{a,b},(#1≥#2&)];

l=NestWhileList[({#[[2]],#[[1]]-IntegerPart[#[[1]]/#[[2]]]#[[2]]}&),{a,b},(#[[2]]>0&)]

Print[Length[l]-1," steps"]

The Euclidean Algorithm is extremely fast. Here is an example of two 2805 - digit numbers :

k=2804;a=IntegerPart[10^k N[π,k]];
b=IntegerPart[10^k N[Exp[1],k]];{a,b}=Sort[{a,b},(#1≥#2&)];

s=TimeUsed[];

l=NestWhileList[({#[[2]],#[[1]]-IntegerPart[#[[1]]/#[[2]]]#[[2]]}&),{a,b},(#[[2]]>0&)]

Last[l]
Print[Length[l]-1," steps"]
Print[TimeUsed[]-s, " sec."]

Mathematica' s  built - in command GCD is substantially faster still :

s=TimeUsed[];

GCD[a,b]

Print[TimeUsed[]-s, " sec."]

The number of digits decreases linearly with respect to the steps taken :

k=50;a=IntegerPart[10^k N[π,k]];
b=IntegerPart[10^k N[Exp[1],k]];{a,b}=Sort[{a,b},(#1≥#2&)];
l=NestWhileList[({#[[2]],#[[1]]-IntegerPart[#[[1]]/#[[2]]]#[[2]]}&),{a,b},(#[[2]]>0&)];
Print[Length[l]-1," steps"]
ListPlot[Log[10,Transpose[l][[2]]],Joined->False,LabelStyle->{Black,Bold,{FontSize->18}},AxesLabel->{"steps", "# digits"}]