Average number of iterations for the Euclidean algorithm to terminate

Question

Let $N$ be a positive integer and $0 \leq s < N$. We try to divide $s$ into $N$ using the Euclidean algorithm:

$N = q_1 s + r_1 $

$r = q_2 r_1 + r_2 $

$\vdots$

$r_{K-1} = q_{K-1} r_K$

If we choose $-r_{i-1}/2 \leq r_i < r_{i-1}/2$, I think this determines the $q_i$'s uniquely, but I don't think this matters for my question.

For a fixed $N$ and $0 \leq s < N$, define $K_s$ to be the number of iterations before the Euclidean algorithm terminates, (i.e. $K$ in the instance written above).

Are there existing tools to characterize $$ \frac{1}{N} \sum_{0 \leq s < N} K_s, $$ for a given $N$?

Answer 1

This algorithm correspons to nearest integer continued fractions or centered continued fraction. The length of such fraction $l(a/b)$ can be expressed in terms of Gauss - Kuz'min statistics for classical continued fraction expansion, see The mean number of steps in the Euclidean algorithm with least absolute value remainders. It means that all results known for for classical continued fractions can be applied in this case as well. In particular average length is known to be $$\dfrac{1}{\varphi(b)}\sum\limits_{1\le a\le b\atop(a,b)=1}l(a/b)= \dfrac{2\log \varphi}{\zeta(2)}\cdot\log b+C+O_{\varepsilon}(b^{-1/6+\varepsilon}).$$

For the recent adnances see The average length of finite continued fractions with fixed denominator by Bykovskii and Frolenkov.

Answer 2

The complexity analysis of the Euclidean algorithm is much much older that the given reference. It goes back to at least Lamé, before 1785. The above answer should be viewed as modern version of Lamé's theorem. The average is actually a normal variable, there are several difficult proofs, see Morris - A short proof that the number of division steps in the Euclidean algorithm is normally distributed, and earlier references.