Geodesic
Asymptotic behaviour of the first and second moments for the number of steps in the Euclidean algorithm
Izvestiya. Mathematics , Tome 72 (2008) no. 5, pp. 1023-1059.

Voir la notice de l'article provenant de la source Math-Net.Ru

We prove asymptotic formulae with two significant terms for the expectation and variance of the random variable $s(c/d)$ when the variables $c$ and $d$ range over the set $1\leq c\leq d\leq R$ and $R\to\infty$, where $s(c,d)=s(c/d)$ is the number of steps in the Euclidean algorithm applied to the numbers $c$ and $d$. 
@article{IM2_2008_72_5_a5,
     author = {A. V. Ustinov},
     title = {Asymptotic behaviour of the first and second moments for the number of steps in the {Euclidean} algorithm},
     journal = {Izvestiya. Mathematics },
     pages = {1023--1059},
     publisher = {mathdoc},
     volume = {72},
     number = {5},
     year = {2008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_2008_72_5_a5/}
}
TY  - JOUR
AU  - A. V. Ustinov
TI  - Asymptotic behaviour of the first and second moments for the number of steps in the Euclidean algorithm
JO  - Izvestiya. Mathematics 
PY  - 2008
SP  - 1023
EP  - 1059
VL  - 72
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IM2_2008_72_5_a5/
LA  - en
ID  - IM2_2008_72_5_a5
ER  - 
%0 Journal Article
%A A. V. Ustinov
%T Asymptotic behaviour of the first and second moments for the number of steps in the Euclidean algorithm
%J Izvestiya. Mathematics 
%D 2008
%P 1023-1059
%V 72
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IM2_2008_72_5_a5/
%G en
%F IM2_2008_72_5_a5
A. V. Ustinov. Asymptotic behaviour of the first and second moments for the number of steps in the Euclidean algorithm. Izvestiya. Mathematics , Tome 72 (2008) no. 5, pp. 1023-1059. http://geodesic.mathdoc.fr/item/IM2_2008_72_5_a5/

[1] D. E. Knuth, The art of computer programming. Vol. 2: Seminumerical algorithms, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley, Reading, MA, 1969 | MR | Zbl

[2] H. Heilbronn, “On the average length of a class of finite continued fractions”, Number Theory and Analysis, Papers in Honor of Edmund Landau, Plenum, New York, 1969, 87–96 | MR | Zbl

[3] J. W. Porter, “On a theorem of Heilbronn”, Mathematika, 22:1 (1975), 20–28 | MR | Zbl

[4] D. E. Knuth, “Evaluation of Porter's constant”, Comput. Math. Appl., 2:2 (1976), 137–139 | DOI | Zbl

[5] J. D. Dixon, “The number of steps in the Euclidean algorithm”, J. Number Theory, 2:4 (1970), 414–422 | DOI | MR | Zbl

[6] D. Hensley, “The number of steps in the Euclidean algorithm”, J. Number Theory, 49:2 (1994), 142–182 | DOI | MR | Zbl

[7] B. Vallée, “A unifying framework for the analysis of a class of Euclidean algorithms”, Theoretical informatics. 4th Latin American symposium (Uruguay, 2000), Lect. Notes Comput. Sci., 1776, Springer, Berlin, 2000, 343–354 | Zbl

[8] V. Baladi, B. Vallée, “Euclidean algorithms are Gaussian”, J. Number Theory, 110:2 (2005), 331–386 | DOI | MR | Zbl

[9] V. A. Bykovskii, “Estimate for dispersion of lengths of continued fractions”, J. Math. Sci. (N. Y.), 146:2 (2007), 5634–5643 | DOI | MR

[10] A. Ya. Khintchine, “Ein Satz über Kettenbrüche, mit arithmetischen Anwendungen”, Math. Z., 18:1 (1923), 289–306 | DOI | MR | MR | Zbl

[11] D. E. Knuth, A. C. Yao, “Analysis of the subtractive algorithm for greatest common divisors”, Proc. Natl. Acad. Sci. USA, 72:12 (1975), 4720–4722 | DOI | MR | Zbl

[12] A. A. Karatsuba, Basic analytic number theory, Springer-Verlag, Berlin, 1993 | MR | MR | Zbl

[13] M. O. Avdeeva, “On the statistics of partial quotients of finite continued fractions”, Funct. Anal. Appl., 38:2 (2004), 79–87 | DOI | MR | Zbl

[14] T. Estermann, “On Kloosterman's sum”, Mathematika, 8 (1961), 83–86 | MR | Zbl

[15] A. V. Ustinov, “On statistical properties of finite continued fractions”, J. Math. Sci. (N. Y.), 137:2 (2006), 4722–4738 | DOI | MR | Zbl

[16] V. A. Bykovskii, “Asymptotic properties of integral points $(a_1,a_2)$, satisfying the congruence $a_1a_2\equiv l\pmod{q}$”, J. Soviet Math., 25:2 (1984), 975–988 | DOI | MR | Zbl | Zbl

[17] L. Lewin, Polylogarithms and associated functions, North Holland, New York, 1981 | MR | Zbl

[18] A. V. Ustinov, “Calculation of the variance in a problem in the theory of continued fractions”, Sb. Math., 198:6, 887–907 | DOI

[19] I. M. Vinogradov, Elements of number theory, Dover Publ., New York, 1954 | MR | Zbl

[20] A. V. Ustinov, “On Gauss–Kuz'min statistics for finite continued fractions”, J. Math. Sci. (N. Y.), 146:2 (2007), 5771–5781 | DOI | MR