Exercise 4.4.10 (Upper bound of the runtime of the Euclidean algorithm)

Question

If the Euclidean algorithm is applied to the positive integers $b$ and $c$, $b\geq c$, then $r_j = (b,c)$ for some $j$, and $r_{j+1} = 0$. Put $E(b,c) = j+1$, so that $E(b,c)$ is the number of divisions performed in executing the algorithm. Show that $E(F_{n+2}, F_{n+1}) = n$ for all positive integers $n$. Prove that $r_j \geq F_2,\ r_{j-1} \geq F_3, \ r_{j-2} \geq F_4, \cdots,$ and that $b \geq F_{j+3}$. More generally, prove that if $F_{n+2} \geq b \geq c$, then $E(b,c) \leq n$, with equality if and only if $b = F_{n+2}$, and $c = F_{n+1}$. Conclude that if $b \geq c$, then $E(b,c) < (\log b)/ \log ((1 + \sqrt{5})/2)$. (This bound was given by Gabriel Lamé in 1845. It was the first occasion in which the worst-case running time of a mathematical algorithm was precisely determined.)

Richard Ganaye · Accepted Answer

ewcommand{\N}{\mathbb{N}}

Example:  With the notations of Theorem 1.1, if we write the Euclidean algorithm for $b= F_5, c = F_4$, we obtain
\begin{align*}
F_5 &= F_4 + F_3 = F_4 q_1 + r_1,\ q_1 = 1,\ 0 < r_1 = F_3  = 2< F_4\ 
F_4 &= F_3 + F_2 = r_1 q_2 + r_2,\ q_2 = 1,\ 0 < r_2 = F_2 = 1 < r_1,\
F_3 &= 2 F_2 + 0  = r_2 q_3 + r_3,\ q_3 = 2,\ 0 < r_3 = 0 < r_2.\
\end{align*}
Since $r_1
e 0, r_2 
e 0$ and $r_3 = 0$, then $j = 2$, and for $n = 3$, $E(F_{n+2}, F_{n+1}) = j+ 1 = 3 = n$.

We note an exception in the last division, where the quotient is not $1$, but $2$, because we divide by $1$. Since $F_2 = F_1 = 1$, $F_3 = F_2 + F_1$ is not a Euclidean division (I fell into this trap first!).

\begin{proof} As in Theorem 1.1, we write the Euclidean algorithm in the form
\begin{align}
& b = r_{-1}, \qquad c = r_0,\
&r_i = r_{i+1} q_{i+2} + r_{i+2},\qquad (-1 \leq i \leq j-1),\
& r_j = b \wedge c, \qquad r_{j+1} = 0.
\end{align}
Here $r_{-1} = b \geq r_0 = c$, and 
\begin{align}
0 < r_{i+2} < r_{i+1},\qquad  	ext{ if } 0 \leq i \leq j-1.
\end{align}
 Then $E(b,c) = j+1$ is the number of divisions performed in executing the algorithm.

\begin{enumerate}
\item[(a)] Suppose that $b = F_{n+2} = r_{-1}$ and $c  = F_{n+1} = r_{0}$. We prove by induction that 
$$\mathscr{P}(i): r_i = F_{n +1 -i}$$
 for $ -1 \leq i  \leq n-1$.
\begin{itemize}
\item $r_{-1} = F_{n+2}$ and $r_0 = F_{n+1}$, so $\mathscr{P}(-1)$ and $\mathscr{P}(0)$ are true.
\item Suppose now that $\mathscr{P}(i)$ and $\mathscr{P}(i+1)$ are true for some $i$, where $-1 \leq i \leq n - 3$. Then
$$r_i = F_{n+1-i}, \qquad r_{i+1} = F_{n-i}.$$
The sequence $(F_k)_{k\geq 2}$ is strictly increasing. Here $i \leq n-3$, thus $ F_{n-i-1} < F_{n-i}$, so
$$
\left\{
\begin{array}{lll}
r_i =  F_{n+1 - i} &= F_{n-i }+ F_{n-i-1},&\quad 0 \leq  F_{n-i-1} < F_{n-i}\
r_i  &=r_{i+1} q_{i+2} + r_{i+2},&\quad 0 \leq r_{i+2} < r_{i+1}
\end{array}
ight.
$$
the unicity of the division gives $q_{i+2} = 1$ and $r_{i+2} = F_{n-i-1}$, thus $\mathscr{P}(i+2)$ is true.

\item The induction is done, so
$$\forall i \in [\![ - 1, n - 1]\!],\ r_i = F_{n + 1-i}.$$
\end{itemize}
In particular, $r_{n-2} = F_3 = 2,\ r_{n-1} = F_2 = 1$, so
$$r_{n-2} = 2 r_{n-1} + 0,$$
thus $r_{n} = 0$, and $j = n - 1$. So 
$$E(F_{n+2}, F_{n+1}) = j + 1 = n.$$

\item[(b)]  We prove by induction on $k$ that
$$\mathscr{Q}(k): r_{j-k} \geq F_{k+2}$$
is true for all $k$ such that $0 \leq k \leq j$.
\begin{itemize}
\item By definition of $j$, $r_{j} 
e 0$, thus $r_j \geq 1 = F_2$, so $\mathscr{Q}(0)$ is true.

Moreover $r_{j-1} > r_j$, so $r_{j-1} \geq r_j + 1 \geq 2 = F_3$, so $\mathscr{Q}(1)$ is true.

\item Suppose that $\mathscr{Q}(k)$ and $\mathscr{Q}(k+1)$ are both true for some $k \leq  j - 2$, so that
\begin{align*}
 r_{j-k} \geq F_{k+2}, \qquad r_{j-k-1} \geq F_{k+3}.
\end{align*}
Then by (2) and (4),
\begin{align*}
r_{j-k-2} &= r_{j-k-1} q_{j-k} + r_{j-k}\
&\geq r_{j-k-1} +  r_{j-k}&(	ext{since } q_{j-k} \geq 1)\
&\geq F_{k+3} + F_{k+2} & 	ext{(by the induction hypothesis )}\
&= F_{k+4}.
\end{align*}
So $r_{j-k-2} \geq F_{k+4}$, which proves $\mathscr{Q}(k+2)$.
\item The induction is done, thus
$$\forall k \in [\![ 0, j ]\!],\ r_{j-k} \geq F_{k+2}.$$
\end{itemize}
In particular, 
\begin{align}
r_1 \geq F_{j+1},\qquad c  = r_0 \geq F_{j+2}.
\end{align}
Since $b \geq c$ and $b = cq_1 + r_1\ (0 \leq r_1 < b)$, then $q_1 \geq 1$,  thus $b \geq c + r_1 \geq F_{j+1} + F_{j+2} = F_{j+3}$, so
\begin{align}
b \geq F_{j+3}.
\end{align}

\item[(c)] Suppose now that $F_{n+2} \geq b \geq c$. Then by (6), $F_{n+2} \geq F_{j+3}$. Since the Fibonacci sequence is strictly increasing from rank $2$, we obtain $n+ 2 \geq j+ 3$ (otherwise $n + 2 < j+ 3$ implies  $F_{n+2} < F_{j+3}$), so
$$n \geq j+ 1 = E(b,c).$$
We saw in part (a) that if $b = F_{n+2}$ and  $c = F_{n+1}$ then $E(b,c) = n$.

Conversely, suppose that $E(b,c) = n$. Then $n = j+1$, thus by (6), $b \geq F_{n+2}$. By hypothesis, $b \leq F_{n+2}$, so $b = F_{n+2}$.

Moreover, by (5) $c \geq F_{j+2} = F_{n+1}$, and $q_1 \geq 1$ since $b \geq c$, thus
$$F_{n+2} = b =cq_1 + r_1 \geq c + r_1 \geq F_{n+1} + r_1,$$
thus $r_1 \leq F_{n+2} - F_{n+1} = F_n$. But $r_1 \geq F_{j+1} = F_n$ by (5), so $r_1 = F_n$.

Then $F_{n+2} = cq_1 + F_n$, thus $cq_1 = F_{n+1}$, where $q_1 \geq 1$, so $c \leq F_{n+1}$ (and $c \geq F_{n+1}$ by (5)), so $c = F_{n+1}$.

In conclusion, if $F_{n+2} \geq b \geq c$, then $E(b,c) \leq n$, with equality if and only if $b = F_{n+2}$, and $c = F_{n+1}$.

\item[(d)] Suppose that $c \leq b$. Since $b$ is a positive integer, there is some positive integer $n$ such that
$$F_{n+1} \leq b \leq F_{n+2}.$$
Since $b \leq F_{n+2}$, then by part (c), $E(b,c) \leq n$.
\begin{itemize}
\item Consider first the worst case, where $E(b,c) = n$. Then, by part (c), $b = F_{n+2}$ and $c = F_{n+1}$. By Problem 3,
$$\left( \frac{1+ \sqrt{5}}{2} ight)^n < F_{n+2} = b,$$
thus
$$E(b,c) = n < \frac{\log(b)}{\log\left( \frac{1+ \sqrt{5}}{2} ight)}.$$

\item If $E(b,c) 
e n$, then $E(b,c) \leq n-1$, and by Problem 3
$$\left( \frac{1+ \sqrt{5}}{2} ight)^{n-1} < F_{n+1} \leq b,$$
thus
$$E(b,c) \leq n- 1 < \frac{\log(b)}{\log\left( \frac{1+ \sqrt{5}}{2} ight)}.$$
 \end{itemize}
 In both cases, 
 $$E(b,c) <  \frac{\log(b)}{\log\left( \frac{1+ \sqrt{5}}{2} ight)}\qquad (b \geq c).$$
\end{enumerate}
\end{proof}

Note: To test these results we can use the following (naive) programs in python, or sagemath:
\begin{verbatim}
def F(n):
    f2, f1 = 1, 0
    for i in range(n):
        f2, f1 = f1, f1 + f2
    return f1
    
def E(b,c):
    counter = 0
    while c != 0:
        b, c = c, b % c
        counter += 1
    return counter
    
n = 4
print(E(F(n+2),F(n+1)))
            4
\end{verbatim}

Exercise 4.4.10 (Upper bound of the runtime of the Euclidean algorithm)

Answers

Comments

Exercise 4.4.10 (Upper bound of the runtime of the Euclidean algorithm)

Answers

Comments

Add answer