Skip to main content
SpringerLink
Log in

Average Bit-Complexity of Euclidean Algorithms

  • Conference paper
  • First Online:
Automata, Languages and Programming (ICALP 2000)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1853))

Included in the following conference series:

Abstract

We obtain new results regarding the precise average bitcomplexity of five algorithms of a broad Euclidean type. We develop a general framework for analysis of algorithms, where the average-case complexity of an algorithm is seen to be 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 an entire class of gcd-like algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Bedford, T., Keane, M., AND Series, C., Eds. Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces, Oxford University Press, 1991.

    Google Scholar 

  2. Bowen, R. Invariant measures for Markov maps of the interval, Commun. Math. Phys. 69 (1979) 1–17.

    Article  MATH  MathSciNet  Google Scholar 

  3. Brent, R.P. Analysis of the binary Euclidean algorithm, Algorithms and Complexity, New directions and recent results, ed. by J.F. Traub, Academic Press 1976, pp 321–355

    Google Scholar 

  4. Daudé, H., Flajolet, P., AND Vallee, B. An average-case analysis of the Gaussian algorithm for lattice reduction, Combinatorics, Probability and Computing (1997) 6 397–433

    Article  MATH  MathSciNet  Google Scholar 

  5. Delance, H. Généralisation du Théoréme d’Ikehara, Ann. Sc. ENS, (1954)71, pp 213–242

    Google Scholar 

  6. Dixon, J. D. The number of steps in the Euclidean algorithm, Journal of Number Theory 2 (1970), 414–422.

    Article  MATH  MathSciNet  Google Scholar 

  7. Flajolet, P. 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, pp 186–210

    Google Scholar 

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

    Google Scholar 

  9. Flajolet, P., AND Vallée, B. Continued fraction Algorithms, Functional operators and Structure constants, Theoretical Computer Science 194 (1998), 1–34.

    Article  MATH  MathSciNet  Google Scholar 

  10. Grothendiek, A. Produits tensoriels topologiques et espaces nucléaires, Mem. Am. Math. Soc. 16 (1955)

    Google Scholar 

  11. Grothendoieck, A. La théorie de Fredholm, Bull. Soc. Math. France 84 pp 319–384.

    Google Scholar 

  12. Heilbronn, H. On the average length of a class of continued fractions, Number Theory and Analysis, ed. by P. Turan, New-York, Plenum, 1969, pp 87–96.

    Google Scholar 

  13. Hensley, D. The number of steps in the Euclidean algorithm, Journal of Number Theory 49,2 (1994), 142–182.

    Article  MATH  MathSciNet  Google Scholar 

  14. Krasnoselskii, M.Positive solutions of operator equations, P. Noordhoff, Groningen, 1964.

    Google Scholar 

  15. 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, pp. 175–222.

    Google Scholar 

  16. Prellberg, T. AND Slawny, J. Maps of intervals with Indifferent fixed points: Thermodynamic formalism and Phase transitions. Journal of Statistical Physics 66 (1992) 503–514

    Article  MATH  MathSciNet  Google Scholar 

  17. Rieger, G. J. Uber die mittlere Schrittazahl bei Divisionalgorithmen, Math. Nachr. (1978) pp 157–180

    Google Scholar 

  18. Rielle, D.Thermodynamic formalism, Addison Wesley (1978)

    Google Scholar 

  19. Relle, D.Dynamical Zeta Functions for Piecewise Monotone Maps of the Interval, vol. 4 of CRM Monograph Series, American Mathematical Society, Providence, 1994.

    Google Scholar 

  20. Tenenbaum, G.Introduction á la théorie analytique des nombres, vol. 13. Institut Élie Cartan, Nancy, France, 1990.

    MATH  Google Scholar 

  21. Vallée, B. Opérateurs de Ruelle-Mayer généralisés et analyse des algorithmes d’Euclide et de Gauss, Acta Arithmetica 81.2 (1997) 101–144.

    MATH  MathSciNet  Google Scholar 

  22. Vallée, B. Fractions continues á contraintes périodiques, Journal of Number Theory 72 (1998) pp 183–235.

    Article  MATH  MathSciNet  Google Scholar 

  23. Vallée, B. Dynamics of the Binary Euclidean Algorithm: Functional Analysis and Operators., Algorithmica (1998) vol 22(4) pp 660–685.

    Article  MATH  MathSciNet  Google Scholar 

  24. Vallée, B. A Unifying Framework for the Analysis of a Class of Euclidean Algorithms., To appear in the proceedings of LATIN’2000, LNCS

    Google Scholar 

  25. Vardi, I. Continued fractions, Preprint, chapter of a book in preparation.

    Google Scholar 

  26. Yao, A.C., AND Knuth, D.E. Analysis of the subtractive algorithm for greatest common divisors. Proc. Nat. Acad. Sc. USA 72 (1975) pp 4720–4722.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. GREYC, Université de Caen, F-14032, Caen, France

    Ali Akhavi & Brigitte Vallée

Authors
  1. Ali Akhavi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Brigitte Vallée
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Sciences, University of Pisa, Corso Italia, 40, 56125, Pisa, Italy

    Ugo Montanari

  2. Center for Computer Sciences, University of Geneva, 24, Rue Général Dufour, 1211, Geneva 4, Switzerland

    José D. P. Rolim

  3. Department of Computer Sciences, ETH Zurich, 8092, Zurich, Switzerland

    Emo Welzl

Rights and permissions

Reprints and permissions

Copyright information

© 2000 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Akhavi, A., Vallée, B. (2000). Average Bit-Complexity of Euclidean Algorithms. In: Montanari, U., Rolim, J.D.P., Welzl, E. (eds) Automata, Languages and Programming. ICALP 2000. Lecture Notes in Computer Science, vol 1853. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45022-X_32

Download citation

  • DOI: https://doi.org/10.1007/3-540-45022-X_32

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-67715-4

  • Online ISBN: 978-3-540-45022-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation