×

Digits and continuants in Euclidean algorithms. Ergodic versus Tauberian theorems. (English) Zbl 0973.11079

The author develops a general analysis of the complexity of Euclidean (or gcd) algorithms, by viewing them as dynamical systems. The reader will be delighted to see in a same paper notions as complexity of continued fraction expansions, transfer operators, Tauberian theorems, and ergodic theory entering the picture. Note that the paper provides analyses of bit-complexities not only for the classical Euclidean algorithms, but also for the binary algorithm, the subtractive algorithm, and algorithms computing Jacobi symbols. A bibliography with 41 references ends the paper.
For a survey on ancient work on this topic, the reader can look at: J. Shallit, Hist. Math. 21, No. 4, 401-419 (1994; Zbl 0859.01004).

MSC:

11K99 Probabilistic theory: distribution modulo \(1\); metric theory of algorithms
68W40 Analysis of algorithms
11K50 Metric theory of continued fractions
11K55 Metric theory of other algorithms and expansions; measure and Hausdorff dimension
68Q25 Analysis of algorithms and problem complexity
37A45 Relations of ergodic theory with number theory and harmonic analysis (MSC2010)
11M99 Zeta and \(L\)-functions: analytic theory
11Y65 Continued fraction calculations (number-theoretic aspects)

Citations:

Zbl 0859.01004
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML EMIS

References:

[1] Akhavi, A., Vallée, B., Average bit-complexity of Euclidean Algorithms. Proceedings of ICALP’00, , pp 373-387, Springer. · Zbl 0973.11102
[2] Babenko, K.I., On a problem of Gauss. Soviet Mathematical Doklady19 (1978), 136-140. · Zbl 0389.10036
[3] T. BEDFORD, M. KEANE, C. SERIES Eds, Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces, Oxford University Press (1991). · Zbl 0743.00040
[4] Beeler, M., Gosper, R.W., Schroeppel, R., HakmemMemorandum 239, M.I.T., Artificial Intelligence Laboratory, Feb. 1972.
[5] Billingsley, P., Ergodic Theory and Information, John Wiley & Sons (1965). · Zbl 0141.16702
[6] Brent, R.P., 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. · Zbl 0373.68040
[7] Brent, R.P., Further analysis of the binary Euclidean algorithm. Report PRG-TR-7-99, Oxford University Computing Laboratory, Nov. 1999 (also reported in [23]).
[8] Cornfeld, I.P., Fomin, S.V., Sinai, Y.G., Ergodic Theory. A series of Comprehensive Studies in Mathematics, Springer-Verlag (1982) · Zbl 0493.28007
[9] Daudé, H., Flajolet, P., Vallée, B., An average-case analysis of the Gaussian algorithm for lattice reduction. Combinatorics, Probability and Computing6 (1997), 397-433. · Zbl 0921.11072
[10] Delange, H., Généralisation du Théorème d’Ikehara. Ann. Sc. ENS71 (1954), 213-242. · Zbl 0056.33101
[11] Dixon, J.D., The number of steps in the Euclidean algorithm. Journal of Number Theory2 (1970), 414-422. · Zbl 0206.33502
[12] Elias, P., Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory. Vol IT-21, No 2, March 1975, 194-203. · Zbl 0298.94011
[13] Faivre, C., Distribution of Lévy’s constants for quadratic numbers. Acta Arithmetica61 (1992), 13-34. · Zbl 0749.11035
[14] Flajolet, P., Analytic analysis of algorithms. In: Proceedings of the 19th International Colloquium “Automata, Languages and Programming”, Vienna, July 1992, W. Kuich, editor, , 186-210. · Zbl 1425.68473
[15] Flajolet, P., Sedgewick, R., Analytic Combinatorics. Book in preparation (1999), see also INRIA Research Reports 1888, 2026, 2376, 2956.
[16] Flajolet, P., Vallée, B., Continued fraction Algorithms, Functional operators and Structure constants. Theoretical Computer Science194 (1998), 1-34. · Zbl 0981.11044
[17] Grothendieck, A., Produits tensoriels topologiques et espaces nucléaires. Mem. Am. Math. Soc.16 (1955). · Zbl 0064.35501
[18] Grothendieck, A., La théorie de Fredholm. Bull. Soc. Math. France84, 319-384. · Zbl 0073.10101
[19] Heilbronn, H., On the average length of a class of continued fractions. Number Theory and Analysis, ed. by P. Turan, New-York, Plenum (1969), 87-96. · Zbl 0212.06503
[20] Hensley, D., The number of steps in the Euclidean algorithm. Journal of Number Theory49 (1994), 142-182. · Zbl 0811.11055
[21] Kato, T., Perturbation Theory for Linear Operators. Springer-Verlag (1980). · Zbl 0435.47001
[22] Khinchin, A.I., Continued Fractions. University of Chicago Press, Chicago (1964). A translation of the Russian original published in 1935. · Zbl 0117.28601
[23] Knuth, D.E., The art of Computer programming, Volume 2. 3rd edition, Addison Wesley, Reading, Massachussets (1998). · Zbl 0895.68055
[24] Krasnoselsky, M., Positive solutions of operator equations. P. Noordhoff, Groningen (1964).
[25] Kuzmin, R.O., Sur un problème de Gauss. Atti del Congresso Internationale dei Matematici 6 (Bologna, 1928), 83-89. · JFM 58.0204.01
[26] Lévy, P.Sur les lois de probabilité dont dépendent les quotients complets et incomplets d’une fraction continue. Bull. Soc. Math. France57 (1929), 178-194. · JFM 55.0916.02
[27] Lorch, E.R., Spectral Theory. Oxford University Press, New York (1962). · Zbl 0105.09204
[28] Mayer, D.H., On a ( function related to the continued fraction transformation. Bulletin de la Société Mathématique de France104 (1976), 195-203. · Zbl 0328.58011
[29] Mayer, D.H., 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. · Zbl 0755.58034
[30] Rieger, G.J., Über die mittlere Schrittazahl bei Divisionalgorithmen. Math. Nachr. (1978), 157-180. · Zbl 0383.10033
[31] Ruelle, D., Thermodynamic formalism. Addison Wesley (1978). · Zbl 0401.28016
[32] Ruelle, D., Dynamical Zeta Functions for Piecewise Monotone Maps of the Interval. CRM Monograph Series 4, American Mathematical Society, Providence (1994). · Zbl 0805.58006
[33] Shapiro, J., Composition operators and classical function theory. Universitext: Tracts in Mathematics, Springer-Verlag (1993). · Zbl 0791.30033
[34] Tenenbaum, G., Introduction à la théorie analytique des nombres. vol. 13. Institut Élie Cartan, Nancy, France (1990). · Zbl 0788.11001
[35] Vallée, B., Fractions continues à contraintes périodiques. Journal of Number Theory72 (1998), 183-235. · Zbl 0918.11047
[36] Vallée, B., Dynamics of the Binary Euclidean Algorithm: Functional Analysis and Operators. Algorithmica22 (1998), 660-685. · Zbl 0914.68106
[37] Vallée, B., A Unifying Framework for the analysis of a class of Euclidean Algorithms. Proceedings of LATIN’2000, , Springer, 343-354. · Zbl 0979.11058
[38] Vallée, B., Dynamical Analysis of a Class of Euclidean Algorithms. Extended version of [37], to appear in Theoretical Computer Science (2001). · Zbl 1044.68164
[39] Vuillemin, J., Exact real computer arithmetic with continued fractions. IEEE Transactions on Computers39, 8 (Aug. 1990), 1087-1105.
[40] Wirsing, E., On the theorem of Gauss-Kusmin-Lévy and a Frobenius-type theorem for function spaces. Acta Arithmetica24 (1974), 507-528. · Zbl 0283.10032
[41] Yao, A.C., Knuth, D.E., Analysis of the subtractive algorithm for greatest common divisors. Proc. Nat. Acad. Sc. USA72 (1975), 4720-4722. · Zbl 0315.10005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.