{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T15:25:26Z","timestamp":1774625126656,"version":"3.50.1"},"reference-count":51,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[2003,3,1]],"date-time":"2003-03-01T00:00:00Z","timestamp":1046476800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3827,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2003,3]]},"DOI":"10.1016\/s0304-3975(02)00652-7","type":"journal-article","created":{"date-parts":[[2003,3,25]],"date-time":"2003-03-25T16:52:06Z","timestamp":1048611126000},"page":"447-486","source":"Crossref","is-referenced-by-count":22,"title":["Dynamical analysis of a class of Euclidean algorithms"],"prefix":"10.1016","volume":"297","author":[{"given":"Brigitte","family":"Vall\u00e9e","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(02)00652-7_BIB1","doi-asserted-by":"crossref","unstructured":"A. Akhavi, B. Vall\u00e9e, Average bit\u2013complexity of Euclidean algorithms, ICALP\u201900, LNCS 1853, pp. 373\u2013387.","DOI":"10.1007\/3-540-45022-X_32"},{"issue":"1","key":"10.1016\/S0304-3975(02)00652-7_BIB2","first-page":"136","article-title":"On a problem of Gauss","volume":"19","author":"Babenko","year":"1978","journal-title":"Soviet Math. Doklady"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB3","doi-asserted-by":"crossref","first-page":"107","DOI":"10.3934\/dcds.1997.3.107","article-title":"A billiard in the hyperbolic plane with decay of correlations of type n\u22122","volume":"3","author":"Bauer","year":"1997","journal-title":"Discrete Continuous Dyn. Systems"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB4","series-title":"Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces","year":"1991"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB5","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1137\/0215025","article-title":"A simple unpredictable random number generator","volume":"15","author":"Blum","year":"1986","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01941319","article-title":"Invariant measures for Markov maps of the interval","volume":"69","author":"Bowen","year":"1979","journal-title":"Comm. Math. Phys."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB7","series-title":"Algorithms and Complexity, New Directions and Recent Results","first-page":"321","article-title":"Analysis of the binary Euclidean algorithm","author":"Brent","year":"1976"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB8","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1017\/S0963548397003258","article-title":"An average-case analysis of the Gaussian algorithm for lattice reduction","volume":"6","author":"Daud\u00e9","year":"1997","journal-title":"Combin. Probab. Comput."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB9","first-page":"213","article-title":"G\u00e9n\u00e9ralisation du Th\u00e9or\u00e8me d'Ikehara","volume":"71","author":"Delange","year":"1954","journal-title":"Ann. Sci. ENS"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB10","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1016\/0022-314X(70)90044-2","article-title":"The number of steps in the Euclidean algorithm","volume":"2","author":"Dixon","year":"1970","journal-title":"J. Number Theory"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB11","first-page":"317","article-title":"Einfacher algorithmus zur Bestimmung der Werthes von (a\/b)","volume":"27","author":"Eisenstein","year":"1944","journal-title":"J. f\u00fcr die Reine Angew. Math."},{"issue":"1","key":"10.1016\/S0304-3975(02)00652-7_BIB12","doi-asserted-by":"crossref","first-page":"13","DOI":"10.4064\/aa-61-1-13-34","article-title":"Distribution of L\u00e9vy's constants for quadratic numbers","volume":"61","author":"Faivre","year":"1992","journal-title":"Acta Arith."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB13","doi-asserted-by":"crossref","unstructured":"P. Flajolet, Analytic analysis of algorithms, in: W. Kuich (Ed.), Proc. 19th Internat. Colloq. \u201cAutomata, Languages and Programming\u201d, Vienna, July 1992, Lecture Notes in Computer Science, vol. 623, Springer, Berlin, pp 186\u2013210.","DOI":"10.1007\/3-540-55719-9_74"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB14","unstructured":"P. Flajolet, R. Sedgewick, Analytic Combinatorics, see also INRIA Research Reports 1888, 2026, 2376, 2956, 1999, in preparation."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00123-0","article-title":"Continued fraction algorithms, functional operators and structure constants","volume":"194","author":"Flajolet","year":"1998","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB16","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","article-title":"Probabilistic encryption","volume":"28","author":"Goldwasser","year":"1984","journal-title":"J. Comput. Systems Sci."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB17","article-title":"Produits tensoriels topologiques et espaces nucl\u00e9aires","volume":"16","author":"Grothendieck","year":"1955","journal-title":"Mem. Am. Math. Soc."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB18","doi-asserted-by":"crossref","first-page":"319","DOI":"10.24033\/bsmf.1476","article-title":"La th\u00e9orie de Fredholm","volume":"84","author":"Grothendieck","year":"1956","journal-title":"Bull. Soc. Math. France"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB19","series-title":"Number Theory and Analysis","first-page":"87","article-title":"On the average length of a class of continued fractions","author":"Heilbronn","year":"1969"},{"issue":"2","key":"10.1016\/S0304-3975(02)00652-7_BIB20","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1006\/jnth.1994.1088","article-title":"The number of steps in the Euclidean algorithm","volume":"49","author":"Hensley","year":"1994","journal-title":"J. Number Theory"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB21","first-page":"113","article-title":"Continued fractions and density results for Dedekind sums","volume":"290","author":"Hickerson","year":"1977","journal-title":"J. Reine Angew. Math."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB22","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1515\/crll.1846.30.166","article-title":"Uber die Kreistheilung und ihre Anwendung auf die Zalhentheorie","volume":"30","author":"Jacobi","year":"1846","journal-title":"J. f\u00fcr die Reine Angew. Math."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB23","series-title":"Perturbation Theory for Linear Operators","author":"Kato","year":"1980"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB24","unstructured":"A.I. Khinchin, Continued Fractions, University of Chicago Press, Chicago, 1964. (A translation of the Russian original published in 1935)."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB25","unstructured":"D.E. Knuth, The Art of Computer Programming, vol. 2, 3rd Edition, Addison-Wesley, Reading, MA, 1998."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB26","doi-asserted-by":"crossref","unstructured":"C. Kraaikamp, A. Lopes, The Theta group and the continued fraction expansion with even partial quotients, 1995, preprint.","DOI":"10.1007\/BF00181695"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB27","unstructured":"M. Krasnoselsky, Positive Solutions of Operator Equations, P. Noordhoff, Groningen, 1964."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB28","unstructured":"R.O. Kuzmin, Sur un probl\u00e8me de Gauss, Atti del Congresso Internationale dei Matematici, vol. 6, Bologna, 1928, pp. 83\u201389."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB29","unstructured":"V.A. Lebesgue, Sur le symbole (a\/b) et quelques unes de ses applications, J. Math. Pures Appl. 12 497\u2013517."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB30","doi-asserted-by":"crossref","first-page":"178","DOI":"10.24033\/bsmf.1150","article-title":"Sur les lois de probabilit\u00e9 dont d\u00e9pendent les quotients complets et incomplets d'une fraction continue","volume":"57","author":"L\u00e9vy","year":"1929","journal-title":"Bull. Soc. Math. France"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB31","series-title":"Spectral Theory","author":"Lorch","year":"1962"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01562537","article-title":"Spectral properties of certain composition operators arising in statistical mechanics","volume":"68","author":"Mayer","year":"1979","journal-title":"Comm. Math. Phys."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB33","series-title":"Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces","first-page":"175","article-title":"Continued fractions and related transformations","author":"Mayer","year":"1991"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB34","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1007\/BF01060077","article-title":"Maps of intervals with Indifferent fixed points","volume":"66","author":"Prellberg","year":"1992","journal-title":"J. Statist. Phys."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB35","doi-asserted-by":"crossref","unstructured":"G.J. Rieger, Uber die mittlere Schrittazahl bei Divisionalgorithmen, Math. Nachr. (1978) 157\u2013180.","DOI":"10.1002\/mana.19780820115"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB36","series-title":"Thermodynamic Formalism","author":"Ruelle","year":"1978"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB37","doi-asserted-by":"crossref","unstructured":"D. Ruelle, Dynamical Zeta Functions for Piecewise Monotone Maps of the Interval, CRM Monograph Series, vol. 4, American Mathematical Society, Providence, RI, 1994.","DOI":"10.1090\/S0273-0979-1994-00489-6"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB38","unstructured":"F. Schweiger, Continued fractions with odd and even partial quotients, Mathematisches Institut der Universitat Salzburg, Arbeitsbericht 2\/1982."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB39","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1016\/S0747-7171(08)80160-5","article-title":"On the worst-case of the three algorithms for computing the Jacobi symbol","volume":"10","author":"Shallit","year":"1990","journal-title":"J. Symbolic Comput."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB40","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1006\/hmat.1994.1031","article-title":"Origins of the analysis of the Euclidean algorithm","volume":"21","author":"Shallit","year":"1994","journal-title":"Historia Math."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB41","series-title":"Composition Operators and Classical Function Theory, Universitext","author":"Shapiro","year":"1993"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB42","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1090\/S0002-9939-1987-0883400-9","article-title":"Compact composition operators on spaces of boundary regular holomorphic functions","volume":"100","author":"Shapiro","year":"1997","journal-title":"Proc. AMS"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB43","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1137\/0206006","article-title":"A fast Monte-Carlo test for primality","volume":"6","author":"Solovay","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB44","unstructured":"G. Tenenbaum, Introduction \u00e0 la th\u00e9orie analytique des nombres, vol. 13, Institut \u00c9lie Cartan, Nancy, France, 1990."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB45","doi-asserted-by":"crossref","first-page":"101","DOI":"10.4064\/aa-81-2-101-144","article-title":"Op\u00e9rateurs de Ruelle\u2013Mayer g\u00e9n\u00e9ralis\u00e9s et analyse des algorithmes d'Euclide et de Gauss","volume":"81.2","author":"Vall\u00e9e","year":"1997","journal-title":"Acta Arith."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB46","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1006\/jnth.1998.2276","article-title":"Fractions continues \u00e0 contraintes p\u00e9riodiques","volume":"72","author":"Vall\u00e9e","year":"1998","journal-title":"J. Number Theory"},{"issue":"4","key":"10.1016\/S0304-3975(02)00652-7_BIB47","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1007\/PL00009246","article-title":"Dynamics of the binary Euclidean algorithm","volume":"22","author":"Vall\u00e9e","year":"1998","journal-title":"Algorithmica"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB48","doi-asserted-by":"crossref","unstructured":"B. Vall\u00e9e, A unifying framework for the analysis of a class of Euclidean algorithms, Proc. LATIN\u20192000, LNCS 1776, Springer, Berlin, pp. 343\u2013354.","DOI":"10.1007\/10719839_34"},{"key":"10.1016\/S0304-3975(02)00652-7_BIB49","unstructured":"I. Vardi, Continued Fractions, preprint (chapter of a book in preparation)."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB50","doi-asserted-by":"crossref","first-page":"507","DOI":"10.4064\/aa-24-5-507-528","article-title":"On the theorem of Gauss\u2013Kusmin\u2013L\u00e9vy and a Frobenius-type theorem for function spaces","volume":"24","author":"Wirsing","year":"1974","journal-title":"Acta Arith."},{"key":"10.1016\/S0304-3975(02)00652-7_BIB51","doi-asserted-by":"crossref","first-page":"4720","DOI":"10.1073\/pnas.72.12.4720","article-title":"Analysis of the subtractive algorithm for greatest common divisors","volume":"72","author":"Yao","year":"1975","journal-title":"Proc. Natl. Acad. Sci. USA"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397502006527?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397502006527?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,12]],"date-time":"2020-03-12T16:57:49Z","timestamp":1584032269000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397502006527"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,3]]},"references-count":51,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2003,3]]}},"alternative-id":["S0304397502006527"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(02)00652-7","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2003,3]]}}}