MHB Number of steps of euclidean algorithm

[evinda]

Hello! (Wave)

I am looking at the following exercise: Let $b=r_0, r_1, r_2, \dots$ be the successive remainders in the Euclidean algorithm applied to $a$ and $b$. Show that after every two steps, the remainder is reduced by at least one half. In other words, verify that $$r_{i+2}< \frac{1}{2} r_i \ ,\text{ for every } i=0,1,2, \dots$$Conclude that the Euclidean algorithm terminates in at most $2 \log_2{(b)}$ steps, where $\log_{2}$ is the logarithm to the base $2$. In particular, show that the number of steps is at most seven times the number of digits in $b$. [ Hint: What is the value of $\log_2{10}$ ?]

I have tried the following:

The general formula for $r_{i-1}$ in the Euclidean algorithm is the following:

$$r_{i-1}=q_{i+1} r_i+r_{i+1}$$So we have: $r_i=q_{i+2} r_{i+1}+r_{i+2} \\=q_{i+2}(q_{i+3} r_{i+2}+r_{i+3})+r_{i+2} \\=q_{i+2} q_{i+3} r_{i+2} +q_{i+2} r_{i+3}+r_{i+2}\\ \geq r_{i+2}+q_{i+2} r_{i+3}+r_{i+2} \\=2r_{i+2}+q_{i+2} r_{i+3}> 2r_{i+2}$

So it follows that $r_{i+2}<\frac{1}{2} r_i$.

As for the number of steps, I have thought the following:We have that $b=r_0>2r_2> 4r_4>8r_6> \dots> 2^m r_{2m}$

The Euclidean algorithm terminates when we find a remainder that is equal to zero.

So we check when $r_{2m}<1$.

$r_{2m}<1 \Rightarrow 2^m r_{2m}<2^m$.

We also have that $2^m r_{2m}<b$.

But from these two inequalities, we cannot find a relation between $m$ and $b$, can we?

 

[Opalg]

We also have that $2^m r_{2m}<b$.

Take logs to base 2 in that inequality: $m + \log_2 r_{2m} < \log_2b$.

If $m > \log_2b$ then $\log_2 r_{2m} < \log_2b - m < 0$. So $r_{2m}<1$, which means that $r_{2m} =0$, and the algorithm has terminated.

Since $m > \log_2b\ \Longrightarrow\ 2m > 2\log_2b$, this shows that as soon as the algorithm reaches the $2m$th step, with $2m > 2\log_2b$, the algorithm will terminate.

 

[Evgeny.Makarov]

The fact that $r_i>2r_{i+2}$ can be shown slightly more easily. We have $r_i>r_{i+1}$ for all $i$ because $r_{i+1}$ is the remainder when something (namely, $r_{i-1}$) is divided by $r_i$. So we have
\[
r_i=q_{i+2}r_{i+1}+r_{i+2}\ge r_{i+1}+r_{i+2}>2r_{i+2}.
\]

 

[evinda]

The fact that $r_i>2r_{i+2}$ can be shown slightly more easily. We have $r_i>r_{i+1}$ for all $i$ because $r_{i+1}$ is the remainder when something (namely, $r_{i-1}$) is divided by $r_i$. So we have
\[
r_i=q_{i+2}r_{i+1}+r_{i+2}\ge r_{i+1}+r_{i+2}>2r_{i+2}.
\]

Yes, I see... (Smile)

 

[evinda]

Take logs to base 2 in that inequality: $m + \log_2 r_{2m} < \log_2b$.

If $m > \log_2b$ then $\log_2 r_{2m} < \log_2b - m < 0$. So $r_{2m}<1$, which means that $r_{2m} =0$, and the algorithm has terminated.

Since $m > \log_2b\ \Longrightarrow\ 2m > 2\log_2b$, this shows that as soon as the algorithm reaches the $2m$th step, with $2m > 2\log_2b$, the algorithm will terminate.

I understand... So the algorithm terminates in at least $2\log_2b$ steps, or not? (Thinking)

In order to show that the number of steps is at least seven times the number of digits in $b$, we use the fact that$$2\log_2b=2\log_2{10} \cdot \log_{10}{b} \approx 6.6 \log_{10}{b}$$

Right?