info prev up next book cdrom email home

Euclidean Algorithm

An Algorithm for finding the Greatest Common Divisor of two numbers $a$ and $b$, also called Euclid's algorithm. It is an example of a P-Problem whose time complexity is bounded by a quadratic function of the length of the input values (Banach and Shallit). Let $a=bq+r$, then find a number $u$ which Divides both $a$ and $b$ (so that $a=su$ and $b=tu$), then $u$ also Divides $r$ since

\begin{displaymath}
r=a-bq=su-qtu=(s-qt)u.
\end{displaymath} (1)

Similarly, find a number $v$ which Divides $b$ and $r$ (so that $b=s'v$ and $r=t'v$), then $v$ Divides $a$ since
\begin{displaymath}
a=bq+r=s'vq+t'v=(s'q+t')v.
\end{displaymath} (2)

Therefore, every common Divisor of $a$ and $b$ is a common Divisor of $b$ and $r$, so the procedure can be iterated as follows
$\displaystyle a$ $\textstyle =$ $\displaystyle bq_1+r_1$ (3)
$\displaystyle b$ $\textstyle =$ $\displaystyle q_2r_1+r_2$ (4)
$\displaystyle r_1$ $\textstyle =$ $\displaystyle q_3r_2+r_3$ (5)
$\displaystyle r_{n-2}$ $\textstyle =$ $\displaystyle q_nr_{n-1}+r_n$ (6)
$\displaystyle r_{n-1}$ $\textstyle =$ $\displaystyle q_{n+1}r_n,$ (7)

where $r_n$ is $\mathop{\rm GCD}\nolimits (a,b)\equiv (a,b)$. Lamé showed that the number of steps needed to arrive at the Greatest Common Divisor for two numbers less than $N$ is
\begin{displaymath}
{\rm steps}\leq {\log_{10} N\over \log_{10}\phi}+{\log_{10}\sqrt{5}\over\log_{10}\phi}
\end{displaymath} (8)

where $\phi$ is the Golden Mean, or $\leq 5$ times the number of digits in the smaller number. Numerically, Lamé's expression evaluates to
\begin{displaymath}
{\rm steps}\leq 4.785\log_{10} N+1.6723.
\end{displaymath} (9)

As shown by Lamé's Theorem, the worst case occurs when the Algorithm is applied to two consecutive Fibonacci Numbers. Heilbronn showed that the average number of steps is $12\ln
2/\pi^2\log_{10} n=0.843\log_{10} n$ for all pairs $(n,b)$ with $b<n$. Kronecker showed that the shortest application of the Algorithm uses least absolute remainders. The Quotients obtained are distributed as shown in the following table (Wagon 1991).

Quotient $\%$
1 41.5
2 17.0
3 9.3

For details, see Uspensky and Heaslet (1939) or Knuth (1973). Let $T(m,n)$ be the number of divisions required to compute $\mathop{\rm GCD}\nolimits (m,n)$ using the Euclidean algorithm, and define $T(m,0)=0$ if $m\geq 0$. Then

\begin{displaymath}
T(m,n)=\cases{
1+T(n,m{\rm\ mod\ }n) & for $m\geq n$\cr
1+T(n,m) & for $m<n$.\cr}
\end{displaymath} (10)

Define the functions
$\displaystyle T(n)$ $\textstyle =$ $\displaystyle {1\over n}\sum_{0\leq m<n} T(m,n)$ (11)
$\displaystyle \tau(n)$ $\textstyle =$ $\displaystyle {1\over\phi(n)} \sum_{\scriptstyle 0\leq m<n\atop\scriptstyle \mathop{\rm GCD}\nolimits (m,n)=1} T(m,n)$ (12)
$\displaystyle A(N)$ $\textstyle =$ $\displaystyle {1\over N^2} \sum_{\scriptstyle 1\leq m\leq N\atop\scriptstyle 1\leq n\leq N} T(m,n),$ (13)

where $\phi$ is the Totient Function, $T(n)$ is the average number of divisions when $n$ is fixed and $m$ chosen at random, $\tau(n)$ is the average number of divisions when $n$ is fixed and $m$ is a random number coprime to $n$, and $A(N)$ is the average number of divisions when $m$ and $n$ are both chosen at random in $[1,N]$. Norton (1990) showed that


\begin{displaymath}
T(n)={12\ln 2\over\pi^2} \left[{\ln n-\sum_{d\vert n}{\Lambd...
...over n}\sum_{d\vert n}\phi(d){\mathcal O} (d^{-1/6+\epsilon}),
\end{displaymath} (14)

where $\Lambda$ is the von Mangoldt Function and $C$ is Porter's Constant. Porter (1975) showed that
\begin{displaymath}
\tau(n)={12\ln 2\over\pi^2}\ln n+C+{\mathcal O}(n^{-1/6}+\epsilon),
\end{displaymath} (15)

and Norton (1990) proved that


\begin{displaymath}
A(N)={12\ln 2\over\pi^2}\left[{\ln N-{\textstyle{1\over 2}}+...
...ght]+C-{\textstyle{1\over 2}}+{\mathcal O}(N^{-1/6+\epsilon}).
\end{displaymath} (16)


There exist 22 Quadratic Fields in which there is a Euclidean algorithm (Inkeri 1947).

See also Ferguson-Forcade Algorithm


References

Bach, E. and Shallit, J. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. Cambridge, MA: MIT Press, 1996.

Courant, R. and Robbins, H. ``The Euclidean Algorithm.'' §2.4 in Supplement to Ch. 1 in What is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 42-51, 1996.

Dunham, W. Journey Through Genius: The Great Theorems of Mathematics. New York: Wiley, pp. 69-70, 1990.

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/porter/porter.html

Inkeri, K. ``Über den Euklidischen Algorithmus in quadratischen Zahlkörpern.'' Ann. Acad. Sci. Fennicae. Ser. A. I. Math.-Phys. 1947, 1-35, 1947.

Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 2nd ed. Reading, MA: Addison-Wesley, 1973.

Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd ed. Reading, MA: Addison-Wesley, 1981.

Norton, G. H. ``On the Asymptotic Analysis of the Euclidean Algorithm.'' J. Symb. Comput. 10, 53-58, 1990.

Porter, J. W. ``On a Theorem of Heilbronn.'' Mathematika 22, 20-28, 1975.

Uspensky, J. V. and Heaslet, M. A. Elementary Number Theory. New York: McGraw-Hill, 1939.

Wagon, S. ``The Ancient and Modern Euclidean Algorithm'' and ``The Extended Euclidean Algorithm.'' §8.1 and 8.2 in Mathematica in Action. New York: W. H. Freeman, pp. 247-252 and 252-256, 1991.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-25