next up previous contents
Next: Prime Numbers Up: Rational numbers Previous: Continued fractions for irrationals   Contents

Complexity of Euclidean Algorithm

Given $ a$ and $ b$, how many steps does it take to find $ (a,b)$. The Euclidean algorithm is good.

Proposition 6.4.2   The Euclidean algorithm will find $ (a,b)$, $ a>b$ in fewer than $ 5 d(b)$ steps, where $ d(b)$ is the number of digits of $ b$ in base $ 10$.

Proof. We look at the worst case scenario. What are the smallest numbers needing $ n$ steps. In this case $ q_i = 1$ for $ 1 \le i < n$ and $ q_n = 2$. Using these $ q_i$'s to calculate $ A_n$ and $ B_n$ we find the Fibonacci numbers, that is the numbers such that $ F_1 = F_2 = 1$, $ F_{i+2} = F_{i+1} + F_i$. We get $ A_n = F_{n+2}$ and $ B_n = F_{n+1}$. So if $ b < F_{n+1}$ then fewer than $ n$ steps will do. If $ b$ has $ d$ digits then

$\displaystyle b \le 10^d -1 \le \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2}
\right)^{5 d + 2} -1 < F_{5 d + 2},
$

as

$\displaystyle F_n = \frac{1}{\sqrt{5}} \left[
\left(\frac{1 + \sqrt{5}}{2}\right)^n -
\left(\frac{1 - \sqrt{5}}{2}\right)^n
\right].$   This will be shown later.$\displaystyle $

$ \qedsymbol$



root 2002-06-10