7
$\begingroup$

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

$\endgroup$
2

2 Answers 2

11
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$
    – soupy
    Sep 21, 2019 at 7:53
  • 2
    $\begingroup$ @soupy Yes, you need to apply Mobius inversion formula. But result will be not so nice-looking, see Knuth, Seminumerical Algorithms. $\endgroup$ Sep 21, 2019 at 8:00
2
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ By "the given reference", do you mean the references given in @AlexeyUstinov's answer? (Also, surely you mean that the number of steps is a normal variable, rather than that the average is a normal variable?) $\endgroup$
    – LSpice
    Sep 24, 2019 at 2:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.