Digits and continuants in euclidean algorithms. Ergodic versus tauberian theorems
Journal de théorie des nombres de Bordeaux, Volume 12 (2000) no. 2, p. 531-570

We obtain new results regarding the precise average-case analysis of the main quantities that intervene in algorithms of a broad Euclidean type. We develop a general framework for the analysis of such algorithms, where the average-case complexity of an algorithm is related to the analytic behaviour in the complex plane of the set of elementary transformations determined by the algorithms. The methods rely on properties of transfer operators suitably adapted from dynamical systems theory and provide a unifying framework for the analysis of the main parameters -digits and continuants- that intervene in an entire class of gcd-like algorithms. We operate a general transfer from the continuous case (Continued Fraction Algorithms) to the discrete case (Euclidean Algorithms), where Ergodic Theorems are replaced by tauberian Theorems.

Nous faisons ici l'analyse en moyenne des principales quantités qui interviennent dans des algorithmes de type Euclide -quotients partiels (chiffres) et continuants-. L'étude de ces paramètres est en particulier essentielle quand on s'intéresse à une mesure très précise (et très réaliste) de la complexité de ces algorithmes, i.e., la complexité en bits, où l'on compte toutes les opérations sur les bits. Nous développons un cadre général pour une telle analyse, où la complexité moyenne est reliée au comportement analytique dans le plan complexe des homographies utilisées par l'algorithme. Nos méthodes sont fondées sur l'utilisation des opérateurs de transfert, objets de base de la théorie des systèmes dynamiques, que nous adaptons à nos besoins. Nous opérons dans un cadre discret, où les théorèmes Taubériens prennent le relais des théorèmes ergodiques. Ainsi, nous obtenons des résultats nouveaux sur la complexité moyenne -mesurée en bits- de toute une classe d'algorithmes de type Euclide, et ce, dans un cadre unificateur.

@article{JTNB_2000__12_2_531_0,
     author = {Vall\'ee, Brigitte},
     title = {Digits and continuants in euclidean algorithms. Ergodic versus tauberian theorems},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     publisher = {Universit\'e Bordeaux I},
     volume = {12},
     number = {2},
     year = {2000},
     pages = {531-570},
     zbl = {0973.11079},
     mrnumber = {1823202},
     language = {en},
     url = {http://www.numdam.org/item/JTNB_2000__12_2_531_0}
}
Vallée, Brigitte. Digits and continuants in euclidean algorithms. Ergodic versus tauberian theorems. Journal de théorie des nombres de Bordeaux, Volume 12 (2000) no. 2, pp. 531-570. http://www.numdam.org/item/JTNB_2000__12_2_531_0/

[1] A. Akhavi, B. Vallée, Average bit-complexity of Euclidean Algorithms. Proceedings of ICALP'00, Lecture Notes in Computer Science 1853, pp 373-387, Springer. | MR 1795906 | Zbl 0973.11102

[2] K.I. Babenko, On a problem of Gauss. Soviet Mathematical Doklady 19 (1978), 136-140. | MR 472746 | Zbl 0389.10036

[3] T. BEDFORD, M. KEANE, C. SERIES Eds, Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces, Oxford University Press (1991). | MR 1130170 | Zbl 0743.00040

[4] M. Beeler, R.W. Gosper, R. Schroeppel, Hakmem. Memorandum 239, M.I.T., Artificial Intelligence Laboratory, Feb. 1972.

[5] P. Billingsley, Ergodic Theory and Information, John Wiley & Sons (1965). | MR 192027 | Zbl 0141.16702

[6] R.P. Brent, Analysis of the Binary Euclidean algorithm. In: Algorithms and Complexity, New directions and recent results, ed. by J.F. Traub, Academic Press (1976), 321-355. | MR 438795 | Zbl 0373.68040

[7] R.P. Brent, Further analysis of the binary Euclidean algorithm. Report PRG-TR-7-99, Oxford University Computing Laboratory, Nov. 1999 (also reported in [23]).

[8] I.P. Cornfeld, S.V. Fomin, Y.G. Sinai, Ergodic Theory. A series of Comprehensive Studies in Mathematics, Springer-Verlag (1982) | MR 832433 | Zbl 0493.28007

[9] H. Daudé, P. Flajolet, B. Vallée, An average-case analysis of the Gaussian algorithm for lattice reduction. Combinatorics, Probability and Computing 6 (1997), 397-433. | MR 1483426 | Zbl 0921.11072

[10] H. Delange, Généralisation du Théorème d'Ikehara. Ann. Sc. ENS 71 (1954), 213-242. | Numdam | MR 68667 | Zbl 0056.33101

[11] J.D. Dixon, The number of steps in the Euclidean algorithm. Journal of Number Theory 2 (1970), 414-422. | MR 266889 | Zbl 0206.33502

[12] P. Elias, Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory. Vol IT-21, No 2, March 1975, 194-203. | MR 373753 | Zbl 0298.94011

[13] C. Faivre, Distribution of Lévy's constants for quadratic numbers. Acta Arithmetica 61 (1992), 13-34. | MR 1153919 | Zbl 0749.11035

[14] P. Flajolet, Analytic analysis of algorithms. In: Proceedings of the 19th International Colloquium "Automata, Languages and Programming", Vienna, July 1992, W. Kuich, editor, Lecture Notes in Computer Science 623, 186-210. | MR 1250638

[15] P. Flajolet, R. Sedgewick, Analytic Combinatorics. Book in preparation (1999), see also INRIA Research Reports 1888, 2026, 2376, 2956.

[16] P. Flajolet, B. Vallée, Continued fraction Algorithms, Functional operators and Structure constants. Theoretical Computer Science 194 (1998), 1-34. | MR 1491644 | Zbl 0981.11044

[17] A. Grothendieck, Produits tensoriels topologiques et espaces nucléaires. Mem. Am. Math. Soc. 16 (1955). | MR 75539 | Zbl 0064.35501

[18] A. Grothendieck, La théorie de Fredholm. Bull. Soc. Math. France 84, 319-384. | Numdam | MR 88665 | Zbl 0073.10101

[19] H. Heilbronn, On the average length of a class of continued fractions. Number Theory and Analysis, ed. by P. Turan, New-York, Plenum (1969), 87-96. | MR 258760 | Zbl 0212.06503

[20] D. Hensley, The number of steps in the Euclidean algorithm. Journal of Number Theory 49 (1994), 142-182. | MR 1305088 | Zbl 0811.11055

[21] T. Kato, Perturbation Theory for Linear Operators. Springer-Verlag (1980). | Zbl 0435.47001

[22] A.I. Khinchin, Continued Fractions. University of Chicago Press, Chicago (1964). A translation of the Russian original published in 1935. | MR 161833 | Zbl 0117.28601

[23] D.E. Knuth, The art of Computer programming, Volume 2. 3rd edition, Addison Wesley, Reading, Massachussets (1998). | MR 633878 | Zbl 0895.68055

[24] M. Krasnoselsky, Positive solutions of operator equations. P. Noordhoff, Groningen (1964). | MR 181881

[25] R.O. Kuzmin, Sur un problème de Gauss. Atti del Congresso Internationale dei Matematici 6 (Bologna, 1928), 83-89. | JFM 58.0204.01

[26] P. Lévy Sur les lois de probabilité dont dépendent les quotients complets et incomplets d'une fraction continue. Bull. Soc. Math. France 57 (1929), 178-194. | JFM 55.0916.02 | Numdam | MR 1504948

[27] E.R. Lorch, Spectral Theory. Oxford University Press, New York (1962). | MR 136967 | Zbl 0105.09204

[28] D.H. Mayer, On a ( function related to the continued fraction transformation. Bulletin de la Société Mathématique de France 104 (1976), 195-203. | Numdam | MR 418168 | Zbl 0328.58011

[29] D.H. Mayer, Continued fractions and related transformations. In: Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces, T. Bedford, M. Keane, and C. Series, Eds. Oxford University Press (1991), 175-222. | MR 1130177 | Zbl 0755.58034

[30] G.J. Rieger, Über die mittlere Schrittazahl bei Divisionalgorithmen. Math. Nachr. (1978), 157-180. | MR 480366 | Zbl 0383.10033

[31] D. Ruelle, Thermodynamic formalism. Addison Wesley (1978). | MR 511655 | Zbl 0401.28016

[32] D. Ruelle, Dynamical Zeta Functions for Piecewise Monotone Maps of the Interval. CRM Monograph Series 4, American Mathematical Society, Providence (1994). | MR 1274046 | Zbl 0805.58006

[33] J. Shapiro, Composition operators and classical function theory. Universitext: Tracts in Mathematics, Springer-Verlag (1993). | MR 1237406 | Zbl 0791.30033

[34] G. Tenenbaum, Introduction à la théorie analytique des nombres. vol. 13. Institut Élie Cartan, Nancy, France (1990). | Zbl 0788.11001

[35] B. Vallée, Fractions continues à contraintes périodiques. Journal of Number Theory 72 (1998), 183-235. | MR 1651691 | Zbl 0918.11047

[36] B. Vallée, Dynamics of the Binary Euclidean Algorithm: Functional Analysis and Operators. Algorithmica 22 (1998), 660-685. | MR 1701635 | Zbl 0914.68106

[37] B. Vallée, A Unifying Framework for the analysis of a class of Euclidean Algorithms. Proceedings of LATIN'2000, Lecture Notes in Computer Science 1776, Springer, 343-354. | Zbl 0979.11058

[38] B. Vallée, Dynamical Analysis of a Class of Euclidean Algorithms. Extended version of [37], to appear in Theoretical Computer Science (2001). | MR 1981160 | Zbl 1044.68164

[39] J. Vuillemin, Exact real computer arithmetic with continued fractions. IEEE Transactions on Computers 39, 8 (Aug. 1990), 1087-1105.

[40] E. Wirsing, On the theorem of Gauss-Kusmin-Lévy and a Frobenius-type theorem for function spaces. Acta Arithmetica 24 (1974), 507-528. | MR 337868 | Zbl 0283.10032

[41] A.C. Yao, D.E. Knuth, Analysis of the subtractive algorithm for greatest common divisors. Proc. Nat. Acad. Sc. USA 72 (1975), 4720-4722. | MR 417041 | Zbl 0315.10005