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



Average number of iterations for the Euclidean algorithm to terminate
This algorithm correspons to [nearest integer continued fractions](http://mathworld.wolfram.com/NearestIntegerContinuedFraction.html) 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](https://link.springer.com/article/10.1134%2FS0001434609010179). 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](http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=sm&paperid=8718&option_lang=eng) by Bykovskii and Frolenkov.


