Digits and continuants in euclidean algorithms. Ergodic versus tauberian theorems

Brigitte Vallée

Journal de théorie des nombres de Bordeaux (2000)

  • Volume: 12, Issue: 2, page 531-570
  • ISSN: 1246-7405

Abstract

top
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.

How to cite

top

Vallée, Brigitte. "Digits and continuants in euclidean algorithms. Ergodic versus tauberian theorems." Journal de théorie des nombres de Bordeaux 12.2 (2000): 531-570. <http://eudml.org/doc/248492>.

@article{Vallée2000,
abstract = {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.},
author = {Vallée, Brigitte},
journal = {Journal de théorie des nombres de Bordeaux},
keywords = {Euclidean algorithms; bit-complexity; Dirichlet series; complexity; gcd; dynamical systems; complexity of continued fraction expansions; transfer operators; Tauberian theorems; ergodic theory; binary algorithm; subtractive algorithm; Jacobi symbols},
language = {eng},
number = {2},
pages = {531-570},
publisher = {Université Bordeaux I},
title = {Digits and continuants in euclidean algorithms. Ergodic versus tauberian theorems},
url = {http://eudml.org/doc/248492},
volume = {12},
year = {2000},
}

TY - JOUR
AU - Vallée, Brigitte
TI - Digits and continuants in euclidean algorithms. Ergodic versus tauberian theorems
JO - Journal de théorie des nombres de Bordeaux
PY - 2000
PB - Université Bordeaux I
VL - 12
IS - 2
SP - 531
EP - 570
AB - 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.
LA - eng
KW - Euclidean algorithms; bit-complexity; Dirichlet series; complexity; gcd; dynamical systems; complexity of continued fraction expansions; transfer operators; Tauberian theorems; ergodic theory; binary algorithm; subtractive algorithm; Jacobi symbols
UR - http://eudml.org/doc/248492
ER -

References

top
  1. [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. Zbl0973.11102MR1795906
  2. [2] K.I. Babenko, On a problem of Gauss. Soviet Mathematical Doklady19 (1978), 136-140. Zbl0389.10036MR472746
  3. [3] T. BEDFORD, M. KEANE, C. SERIES Eds, Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces, Oxford University Press (1991). Zbl0743.00040MR1130170
  4. [4] M. Beeler, R.W. Gosper, R. Schroeppel, Hakmem.Memorandum 239, M.I.T., Artificial Intelligence Laboratory, Feb. 1972. 
  5. [5] P. Billingsley, Ergodic Theory and Information, John Wiley & Sons (1965). Zbl0141.16702MR192027
  6. [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. Zbl0373.68040MR438795
  7. [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. [8] I.P. Cornfeld, S.V. Fomin, Y.G. Sinai, Ergodic Theory. A series of Comprehensive Studies in Mathematics, Springer-Verlag (1982) Zbl0493.28007MR832433
  9. [9] H. Daudé, P. Flajolet, B. Vallée, An average-case analysis of the Gaussian algorithm for lattice reduction. Combinatorics, Probability and Computing6 (1997), 397-433. Zbl0921.11072MR1483426
  10. [10] H. Delange, Généralisation du Théorème d'Ikehara. Ann. Sc. ENS71 (1954), 213-242. Zbl0056.33101MR68667
  11. [11] J.D. Dixon, The number of steps in the Euclidean algorithm. Journal of Number Theory2 (1970), 414-422. Zbl0206.33502MR266889
  12. [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. Zbl0298.94011MR373753
  13. [13] C. Faivre, Distribution of Lévy's constants for quadratic numbers. Acta Arithmetica61 (1992), 13-34. Zbl0749.11035MR1153919
  14. [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. MR1250638
  15. [15] P. Flajolet, R. Sedgewick, Analytic Combinatorics. Book in preparation (1999), see also INRIA Research Reports 1888, 2026, 2376, 2956. 
  16. [16] P. Flajolet, B. Vallée, Continued fraction Algorithms, Functional operators and Structure constants. Theoretical Computer Science194 (1998), 1-34. Zbl0981.11044MR1491644
  17. [17] A. Grothendieck, Produits tensoriels topologiques et espaces nucléaires. Mem. Am. Math. Soc.16 (1955). Zbl0064.35501MR75539
  18. [18] A. Grothendieck, La théorie de Fredholm. Bull. Soc. Math. France84, 319-384. Zbl0073.10101MR88665
  19. [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. Zbl0212.06503MR258760
  20. [20] D. Hensley, The number of steps in the Euclidean algorithm. Journal of Number Theory49 (1994), 142-182. Zbl0811.11055MR1305088
  21. [21] T. Kato, Perturbation Theory for Linear Operators. Springer-Verlag (1980). Zbl0435.47001
  22. [22] A.I. Khinchin, Continued Fractions. University of Chicago Press, Chicago (1964). A translation of the Russian original published in 1935. Zbl0117.28601MR161833
  23. [23] D.E. Knuth, The art of Computer programming, Volume 2. 3rd edition, Addison Wesley, Reading, Massachussets (1998). Zbl0895.68055MR633878
  24. [24] M. Krasnoselsky, Positive solutions of operator equations. P. Noordhoff, Groningen (1964). MR181881
  25. [25] R.O. Kuzmin, Sur un problème de Gauss. Atti del Congresso Internationale dei Matematici 6 (Bologna, 1928), 83-89. JFM58.0204.01
  26. [26] P. LévySur les lois de probabilité dont dépendent les quotients complets et incomplets d'une fraction continue. Bull. Soc. Math. France57 (1929), 178-194. Zbl55.0916.02MR1504948JFM55.0916.02
  27. [27] E.R. Lorch, Spectral Theory. Oxford University Press, New York (1962). Zbl0105.09204MR136967
  28. [28] D.H. Mayer, On a ( function related to the continued fraction transformation. Bulletin de la Société Mathématique de France104 (1976), 195-203. Zbl0328.58011MR418168
  29. [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. Zbl0755.58034MR1130177
  30. [30] G.J. Rieger, Über die mittlere Schrittazahl bei Divisionalgorithmen. Math. Nachr. (1978), 157-180. Zbl0383.10033MR480366
  31. [31] D. Ruelle, Thermodynamic formalism. Addison Wesley (1978). Zbl0401.28016MR511655
  32. [32] D. Ruelle, Dynamical Zeta Functions for Piecewise Monotone Maps of the Interval. CRM Monograph Series 4, American Mathematical Society, Providence (1994). Zbl0805.58006MR1274046
  33. [33] J. Shapiro, Composition operators and classical function theory. Universitext: Tracts in Mathematics, Springer-Verlag (1993). Zbl0791.30033MR1237406
  34. [34] G. Tenenbaum, Introduction à la théorie analytique des nombres. vol. 13. Institut Élie Cartan, Nancy, France (1990). Zbl0788.11001
  35. [35] B. Vallée, Fractions continues à contraintes périodiques. Journal of Number Theory72 (1998), 183-235. Zbl0918.11047MR1651691
  36. [36] B. Vallée, Dynamics of the Binary Euclidean Algorithm: Functional Analysis and Operators. Algorithmica22 (1998), 660-685. Zbl0914.68106MR1701635
  37. [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. Zbl0979.11058
  38. [38] B. Vallée, Dynamical Analysis of a Class of Euclidean Algorithms. Extended version of [37], to appear in Theoretical Computer Science (2001). Zbl1044.68164MR1981160
  39. [39] J. Vuillemin, Exact real computer arithmetic with continued fractions. IEEE Transactions on Computers39, 8 (Aug. 1990), 1087-1105. 
  40. [40] E. Wirsing, On the theorem of Gauss-Kusmin-Lévy and a Frobenius-type theorem for function spaces. Acta Arithmetica24 (1974), 507-528. Zbl0283.10032MR337868
  41. [41] A.C. Yao, D.E. Knuth, Analysis of the subtractive algorithm for greatest common divisors. Proc. Nat. Acad. Sc. USA72 (1975), 4720-4722. Zbl0315.10005MR417041

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.