Digits and continuants in euclidean algorithms. Ergodic versus tauberian theorems

Vallée, Brigitte

Journal de théorie des nombres de Bordeaux, Tome 12 (2000) no. 2, pp. 531-570.

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.

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.

[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 | Zbl

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

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

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

[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 | Zbl

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

[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

[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 | Zbl

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

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

[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 | Zbl

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

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

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

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

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

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

[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 | Numdam | MR

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

[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 | Zbl

[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 | Zbl

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

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

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

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

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

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

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

[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

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

[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 | Zbl

[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 | Zbl