The mean number of steps in the Euclidean algorithm with least absolute value remainders (Q1033905): Difference between revisions

It is well known that the Euclidean algorithm in which the remainders \[ a=bq+r, \qquad q=\left[\frac{a}{b}+\frac{1}{2} \right], \qquad -\frac{q}{2} \leq r < \frac{q}{2} \] with least absolute values are chosen leads to the decomposition in a continued fraction \[ \frac{a}{b}=t_0+\cfrac{{\varepsilon_1}}{ t_1+\cfrac{{\varepsilon_2}}{ t_2+ \ddots + \cfrac{{\varepsilon_l}}{{t_l}}}} \] of length \(l=l(a/b)\), where \(t_0\) is an integer, \(t_1,t_2,\dots,t_l\) are positive integers, and \[ \varepsilon_k=\pm 1, t_k \geq 2, k=1,\dots,l, \; t_k+\varepsilon_{k+1}\geq 2, k=1,\dots,l-1. \] Two estimations for the mean number of steps in the Euclidean algorithm with the choice of least absolute value remainders are obtained in the paper. The bibliography contains 5 sources.