Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Numeration and discrete dynamical systems

  • Published:
Computing Aims and scope Submit manuscript

Abstract

This survey aims at giving both a dynamical and computer arithmetic-oriented presentation of several classical numeration systems, by focusing on the discrete dynamical systems that underly them: this provides simple algorithmic generation processes, information on the statistics of digits, on the mean behavior, and also on periodic expansions (whose study is motivated, among other things, by finite machine simulations). We consider numeration systems in a broad sense, that is, representation systems of numbers that also include continued fraction expansions. These numeration systems might be positional or not, provide unique expansions or be redundant. Special attention will be payed to β-numeration (one expands a positive real number with respect to the base β > 1), to continued fractions, and to their Lyapounov exponents. In particular, we will compare both representation systems with respect to the number of significant digits required to go from one type of expansion to the other one, through the discussion of extensions of Lochs’ theorem.

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

Access this article

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

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Akiyama S, Barat G, Berthé V, Siegel A (2008) Boundary of central tiles associated with Pisot beta-numeration and purely periodic expansions. Monatsh Math 155: 377–419

    Article  MathSciNet  MATH  Google Scholar 

  2. Arnold VI (1998) Higher-dimensional continued fractions. Regul Chaotic Dyn 3: 10–17

    Article  MATH  Google Scholar 

  3. Avizienis A (1961) Signed-digit number representations for fast parallel arithmetic. IEEE Trans EC-10: 389–400

    MathSciNet  Google Scholar 

  4. Bajard J-C, Muller J-M (eds) (2004) Calcul et arithmétique des ordinateurs, Traité IC2, série Informatique et Systèmes d’Information, Hermes Sciences

  5. Baladi V, Vallée B (2005) Euclidean algorithms are Gaussian. J Number Theory 110: 331–386

    Article  MathSciNet  MATH  Google Scholar 

  6. Barat G, Liardet P (2004) Dynamical systems originated in the Ostrowski alpha-expansion. Ann Univ Sci Budapest Sect Comput 24: 133–184

    MathSciNet  MATH  Google Scholar 

  7. Barat G, Berthé V, Liardet P, Thuswaldner JM (2006) Dynamical directions in numeration. Ann Inst Fourier (Grenoble) 56: 1987–2092

    Article  MathSciNet  MATH  Google Scholar 

  8. Barreira L, Godofredo I (2008) Partial quotients of continued fractions and β-expansions. Nonlinearity 21: 2211–2219

    Article  MathSciNet  MATH  Google Scholar 

  9. Berthé V (2001) Autour du système de numération d’Ostrowski. Bull Belg Math Soc Simon Stevin 8: 209–239

    MathSciNet  MATH  Google Scholar 

  10. Berthé V (2011) Multidimensional Euclidean algorithms, numeration and substitutions. Integers (to appear)

  11. Berthé V, Imbert L (2009) Diophantine approximation, Ostrowski numeration and the double-base number system. Discret Math Theor Comput Sci 11: 153–172

    MATH  Google Scholar 

  12. Berthé V, Nakada H (2000) On continued fraction expansions in positive characteristic: equivalence relations and some metric properties. Expo Math 18: 257–284

    MathSciNet  MATH  Google Scholar 

  13. Berthé V, Rigo M (2005) Abstract numeration systems and tilings. In: Proceedings of the 30th international symposium: mathematical foundations of computer science (Gdańsk 2005). Lecture Notes in Computer Science 3618, pp 131–143

  14. Bertrand A (1977) Développements en base de Pisot et répartition modulo 1. C R Acad Sci Paris Sér A-B 285(6): A419–A421

    MathSciNet  Google Scholar 

  15. Billingsley P (1965) Ergodic theory and information. Wiley, New York

    MATH  Google Scholar 

  16. Blanchard F (2009) Topological chaos: what may this mean?. J Differ Equ Appl 15: 23–46

    Article  MathSciNet  MATH  Google Scholar 

  17. Boese G (1982) An a priori estimate for the truncation error of a continued fraction expansion to the Gaussian error function. Computing 29: 135–152

    Article  MathSciNet  MATH  Google Scholar 

  18. Bosma W (2001) Signed bits and fast exponentiation. J Théor Nombres Bordeaux 13: 27–41

    Article  MathSciNet  MATH  Google Scholar 

  19. Bosma W, Dajani K, Kraaikamp C (2006) Entropy quotients and correct digits in number-theoretic expansions, dynamics and stochastics. IMS Lect Notes Monogr Ser 48: 176–188

    Article  MathSciNet  Google Scholar 

  20. Brentjes AJ (1981) Multi-dimensional continued fraction algorithms. Mathematical Centre Tracts. Matematisch Centrum, Amsterdam

    Google Scholar 

  21. Broise A (1996) Fractions continues multidimensionnelles et lois stables. Bull Soc Math France 124: 97–139

    MathSciNet  MATH  Google Scholar 

  22. Broise-Alamichel A, Guivarc’h Y (2001) Exposants caractéristiques de l’algorithme de Jacobi-Perron et de la transformation associée. Ann Inst Fourier (Grenoble) 51: 565–686

    Article  MathSciNet  MATH  Google Scholar 

  23. Cesaratto E, Clément J, Daireaux B, Lhote L, Maume-Deschamps V, Vallée B (2009) Regularity of the Euclid algorithm; application to the anaysis of fast GCD algorithms. J Symb Comput 44: 726–767

    Article  MATH  Google Scholar 

  24. Choe GH (2005) Computational ergodic theory. Algorithms and Computation in Mathematics. Springer, Berlin

    Google Scholar 

  25. Corless RM (1992) Continued fractions and chaos. Am Math Mon 99: 203–215

    Article  MathSciNet  MATH  Google Scholar 

  26. Corless RM (1994) What good are numerical simulations of chaotic dynamical systems?. Comput Math Appl 28: 107–121

    Article  MathSciNet  MATH  Google Scholar 

  27. Corless RM, Frank GW, Monroe JG (1990) Chaos and continued fractions. Phys D 46: 241–253

    Article  MathSciNet  MATH  Google Scholar 

  28. Cuyt A, Verdonk B, Waadeland H (2006) Efficient and reliable multiprecision implementation of elementary and special functions. SIAM J Sci Comput 28: 1437–1462

    Article  MathSciNet  MATH  Google Scholar 

  29. Dajani K, Fieldsteel A (2001) Equipartition of interval partitions and an application to number theory. Proc Am Math Soc 129: 3453–3460

    Article  MathSciNet  MATH  Google Scholar 

  30. Dajani K, Kraaikamp C (2002) Ergodic theory of numbers. The Mathematical Association of America, Washington, DC

    MATH  Google Scholar 

  31. Devaney RL (1989) An introduction to chaotic dynamical systems. Addison–Wesley studies in nonlinearity, Redwood City

    MATH  Google Scholar 

  32. Faivre C (1997) On decimal and continued fraction expansions of a real number. Acta Arith 82: 119–128

    MathSciNet  MATH  Google Scholar 

  33. Faivre C (1998) A central limit theorem related to decimal and continued fraction expansion. Arch Math (Basel) 70: 455–463

    Article  MathSciNet  MATH  Google Scholar 

  34. Faivre C (2001) On calculating a continued fraction expansion from a decimal expansion. Acta Sci Math (Szeged) 67: 505–519

    MathSciNet  MATH  Google Scholar 

  35. Flajolet P, Odlyzko AM (1990) Random mapping statistics, EUROCRYPT’ 89. Lect Notes Comput Sci 434: 329–354

    Article  MathSciNet  Google Scholar 

  36. Flajolet P, Vallée B (2000) Continued fractions, comparison algorithms, and fine structure constants. In: CMS Conference Proceedings, vol 27. American Mathematical Society, Providence, pp 53–82

  37. Flajolet P, Vallée B (1998) Continued fraction algorithms, functional operators, and structure constants. Theoret Comput Sci 194: 1–34

    Article  MathSciNet  MATH  Google Scholar 

  38. Frougny Ch (2002) Numeration systems. Encyclopedia of Mathematics and its Applications, vol 90, chap 7. Cambridge University Press, Cambridge, pp 230–268

  39. Frougny Ch (2003) On-line digit set conversion in real base. Theoret Comput Sci 292: 221–235

    Article  MathSciNet  MATH  Google Scholar 

  40. Frougny Ch (2000) On-the-fly algorithms and sequential machines. IEEE Trans Comput 49: 859–863

    Article  MathSciNet  Google Scholar 

  41. Frougny Ch (1999) On-line finite automata for addition in some numeration systems. Theor Inf Appl 33: 79–101

    Article  MathSciNet  MATH  Google Scholar 

  42. Frougny Ch (1997) On the sequentiality of the successor function. Inf Comput 139: 17–38

    Article  MathSciNet  MATH  Google Scholar 

  43. Frougny Ch, Sakarovitch J (2010) Number representation and finite automata. Encyclopedia of Mathematics and its Applications, vol 135, chap 2. Cambridge University Press, Cambridge, pp 34–107

  44. Galatolo S, Hoyrup M, Rojas C (2010) Effective symbolic dynamics, random points, statistical behavior, complexity and entropy. Inf Comput 208: 23–41

    Article  MathSciNet  MATH  Google Scholar 

  45. Góra P, Boyarsky A (1988) Why computers like Lebesgue measure. Comput Math Appl 16: 321–329

    Article  MathSciNet  MATH  Google Scholar 

  46. Góra P, Paweł , Boyarsky A, Shafiqul IMd, Bahsoun W (2006) Absolutely continuous invariant measures that cannot be observed experimentally. SIAM J Appl Dyn Syst 5:84–90

  47. Gosper W (1972) Continued fraction arithmetic, HAKMEM Item 101B. MIT Artificial Intelligence Memo 239. MIT

  48. Grabner PJ, Heuberger C (2006) On the number of optimal base 2 representations of integers. Des Codes Cryptogr 40: 25–39

    Article  MathSciNet  Google Scholar 

  49. Grabner PJ, Liardet P, Tichy RF (1995) Odometers and systems of numeration. Acta Arith LXX.2: 103–123

    MathSciNet  Google Scholar 

  50. Grabner PJ, Heuberger C, Prodinger H, Thuswaldner JM (2005) Analysis of linear combination algorithms in cryptography. ACM Trans Algorithms 1: 123–142

    Article  MathSciNet  Google Scholar 

  51. Hardy GH, Wright EM (1979) An introduction to the theory of numbers. Oxford Science Publications, Oxford

    MATH  Google Scholar 

  52. Heuberger C, Prodinger H. (2001) On minimal expansions in redundant number systems: Algorithms and quantitative analysis. Computing 66: 377–393

    Article  MathSciNet  MATH  Google Scholar 

  53. Ito S (1986) Some skew product transformations associated with continued fractions and their invariant measures. Tokyo J Math 9: 115–133

    Article  MathSciNet  MATH  Google Scholar 

  54. Ito S, Nakada H (1988) Approximations of real numbers by the sequence {nα} and their metrical theory. Acta Math Hung 52: 91–100

    Article  MathSciNet  MATH  Google Scholar 

  55. Jones WB, Thron WJ (1980) Continued fractions. Encyclopedia of Mathematics and its Applications, vol 11. Addison–Wesley Publishing Co, Reading

    Google Scholar 

  56. Kátai I, Szabó J (1975) Canonical Number Systems for Complex Integers. Acta Sci Math (Szeged) 37: 255–260

    MathSciNet  MATH  Google Scholar 

  57. Khintchine AY (1963) Continued fractions (translated by P. Wynn). P. Noordhoff Ltd, Groningen

    Google Scholar 

  58. Kitchens BP (1998) Symbolic dynamics, One-sided, two-sided and countable state Markov shifts (Universitext). Springer, Berlin

    Google Scholar 

  59. Knuth DE (1998) The art of computer programming. Seminumerical algorithms. Addison–Wesley, Reading

    Google Scholar 

  60. Kornerup P, Matula D (1995) LCF: a lexicographic binary representation of the rationals. J Univ Comput Sci 1: 484–503

    MathSciNet  MATH  Google Scholar 

  61. Lagarias JC (1982) Best simultaneous diophantine approximations. I. Growth rates of best approximation denominators. Trans Am Math Soc 272: 545–554

    MathSciNet  MATH  Google Scholar 

  62. Lagarias JC (1982) Best simultaneous diophantine approximations. II. Behavior of consecutive best approximations. Pac J Math 102: 61–88

    MathSciNet  MATH  Google Scholar 

  63. Lagarias JC (1985) The computational complexity of simultaneous Diophantine approximation problems. SIAM J Comput 14: 196–209

    Article  MathSciNet  MATH  Google Scholar 

  64. Lefèvre V (2005) New results on the distance between a segment and \({\mathbb{Z}^{2}}\) . Application to exact rounding. In: Proceedings of the 17th IEEE symposium on computer arithmetic, pp 68–75

  65. Lefèvre V, Muller J-M, Tisserand A (1998) Towards correctly rounded transcendentals. IEEE Trans Comput 47: 1235–1243

    Article  Google Scholar 

  66. Lester DR (2001) Effective continued fractions. In: Burgess N, Ciminiera L (eds) 15th IEEE Symposium on Computer Arithmetic: ARITH-15, pp 163–172

  67. Li B, Wu J (2008) Beta-expansion and continued fraction expansion over formal Laurent series. Finite Fields Appl 14: 635–647

    Article  MathSciNet  MATH  Google Scholar 

  68. Li B, Wu J (2008) Beta-expansion and continued fraction expansion. J Math Anal Appl 339: 1322–1331

    Article  MathSciNet  MATH  Google Scholar 

  69. Lind D, Marcus B (1995) An introduction to symbolic dynamics and coding. Cambridge University Press, Cambridge

    Book  MATH  Google Scholar 

  70. Lochs G (1964) Vergleich der Genauigkeit von Dezimalbruch und Kettenbruch. Abh Math Sem Univ Hamburg 27: 142–144

    Article  MathSciNet  MATH  Google Scholar 

  71. Lochs G (1963) Die ersten 968 Kettenbruchnenner von π. Monatsh Math 67: 311–316

    Article  MathSciNet  MATH  Google Scholar 

  72. Lhote L, Vallée B (2008) Gaussian laws for the main parameters of the Euclid algorithms. Algorithmica 50: 497–554

    Article  MathSciNet  MATH  Google Scholar 

  73. Ménissier-Morain V (1994) Arithmétique exacte, conception, algorithmique et performances d’une implémentation informatique en précision arbitraire, Thèse, Université Paris 7

  74. Muller J-M (1989) Arithmétique des Ordinateurs. Masson, Paris

    Google Scholar 

  75. Muller J-M (1997) Elementary functions, algorithms and implementation. Birkhäuser Boston Inc., Boston

    MATH  Google Scholar 

  76. Muller J-M (1994) Some characterizations of functions computable in on-line arithmetic. IEEE Trans Comput 43: 752–755

    Article  MathSciNet  MATH  Google Scholar 

  77. Muller J-M, Brisebarre N, de Dinechin F, Jeannerod C-P, Lefèvre V, Melquiond G, Revol N, Stehlé D, Torres S (2010) Handbook of floating-point arithmetic. Birkhäuser Boston Inc, Boston

    Book  MATH  Google Scholar 

  78. Niederreiter H (1987) Continued fractions for formal power series, pseudorandom numbers, and linear complexity. Contributions to general algebra, 5 (Salzburg, 1986). Hölder-Pichler-Tempsky, Vienna, pp 221–233

  79. Niederreiter H (1995) Low-discrepancy sequences and non-Archimedean Diophantine approximations. Stud Sci Math Hung 30: 111–122

    MathSciNet  MATH  Google Scholar 

  80. Niederreiter H (1988) Sequences with almost perfect linear complexity profile. In: Chaum D, Price WL (eds) Advances in cryptology: Proc. EUROCRYPT’87”. Springer, Berlin, pp 37–51

  81. Niqui M (2007) Exact arithmetic on the Stern-Brocot tree. J Discret algorithms 5: 356–379

    MathSciNet  MATH  Google Scholar 

  82. Nguyen, PQ, Vallée, B (eds) (2010) The LLL algorithm, survey and applications. Information Security and Cryptography. Springer, Dordrecht

    Google Scholar 

  83. Parry W, Pollicott M (1990) Zeta functions and the periodic orbit structure of hyperbolic dynamics, Astérisque, pp 187–188

  84. Pilyugin SY (1999) Shadowing in dynamical systems. Lecture Notes in Mathematics 1706. Springer, Berlin

    Google Scholar 

  85. Pollicott M (1986) Distribution of closed geodesics on the modular surface and quadratic irrationals. Bull Soc Math France 114: 431–446

    MathSciNet  MATH  Google Scholar 

  86. Raney GN (1973) On continued fractions and finite automata. Math Ann 206: 265–283

    Article  MathSciNet  MATH  Google Scholar 

  87. Rényi A (1957) Representations for real numbers and their ergodic properties. Acta Math Acad Sci Hung 8: 477–493

    Article  MATH  Google Scholar 

  88. Schmidt K (1980) On periodic expansions of Pisot numbers and Salem numbers. Bull Lond Math Soc 12: 269–278

    Article  MATH  Google Scholar 

  89. Schweiger F (2000) Multi-dimensional continued fractions. Oxford Science Publications, Oxford Univ. Press, Oxford

    Google Scholar 

  90. Sidorov N et al (2003) Arithmetic dynamics. In: Bezuglyi S (eds) Topics in dynamics and ergodic theory. London Mathematical Society Lecture Note Series, vol 310. Cambridge University Press, Cambridge, pp 145–189

    Google Scholar 

  91. Skokos Ch (2010) The Lyapunov Characteristic Exponents and their Computation. Lect Notes Phys 790: 63–135

    Article  Google Scholar 

  92. Tamura J-I, Yasutomi S-I (2009) A new multidimensional continued fraction algorithm. Math Comput 78: 2209–2222

    Article  MathSciNet  MATH  Google Scholar 

  93. Vallée B (2006) Euclidean dynamics. Discret Contin Dyn Syst 15: 281–352

    Article  MATH  Google Scholar 

  94. Vuillemin J (1990) Exact real computer arithmetic with continued fractions. IEEE Trans Comput 39: 1087–1105

    Article  Google Scholar 

  95. V’yugin VV (1998) Ergodic theorems for individual random sequences. Theor Comput Sci 207: 343–361

    Article  MathSciNet  MATH  Google Scholar 

  96. Wall HS (1948) Analytic theory of continued fractions. D. Van Nostrand Company, Inc., New York

    MATH  Google Scholar 

  97. Walters P (1982) An introduction to ergodic theory. Springer, New York

    Book  MATH  Google Scholar 

  98. Wu J (2006) Continued fraction and decimal expansions of an irrational number. Adv Math 206: 684–694

    Article  MathSciNet  MATH  Google Scholar 

  99. Wu J (2008) An iterated logarithm law related to decimal and continued fraction expansions. Monatsh Math 153: 83–87

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Laboratoire d’Informatique Algorithmique, Fondements et Applications, Université Paris Diderot, Paris 7, Case 7014, 75205, Paris Cedex 13, France

    V. Berthé

Authors
  1. V. Berthé
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to V. Berthé.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Berthé, V. Numeration and discrete dynamical systems. Computing 94, 369–387 (2012). https://doi.org/10.1007/s00607-011-0181-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00607-011-0181-9

Keywords

Mathematics Subject Classification (2000)

Search

Navigation