# Average number of iterations for the Euclidean algorithm to terminate

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$$?

• I think this is discussed in detail in Knuth, Seminumerical Algorithms. Sep 20, 2019 at 22:21
• Here sci-hub.se/https://iopscience.iop.org/article/10.1070/SM8718/… you can find a rather precise answer if you're interested in $s$ comprime to $N$. Perhaps not surprisingly the answer is of order $O(\log{N})$. Sep 20, 2019 at 22:35

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}).$$
• These are really interesting results! I'm a bit embarrassed to not notice the connection to continued fractions. Correct me if I'm wrong, but I imagine it would not be difficult to get estimates for $\sum_{1\leq a<b} l(a/b)$ and not just for $(a,b)=1$. Sep 21, 2019 at 7:53