February  2006, 15(1): 281-352. doi: 10.3934/dcds.2006.15.281

Euclidean dynamics

1. 

GREYC, UMR CNRS 6072, University of Caen, Batiment Sciences 3, Campus II, F-14032 Caen, France

Received  December 2004 Revised  October 2005 Published  February 2006

We study a general class of Euclidean algorithms which compute the greatest common divisor [gcd], and we perform probabilistic analyses of their main parameters. We view an algorithm as a dynamical system restricted to rational inputs, and combine tools imported from dynamics, such as transfer operators, with various tools of analytic combinatorics: generating functions, Dirichlet series, Tauberian theorems, Perron's formula and quasi-powers theorems. Such dynamical analyses can be used to perform the average-case analysis of algorithms, but also (dynamical) analysis in distribution.
Citation: Brigitte Vallée. Euclidean dynamics. Discrete & Continuous Dynamical Systems - A, 2006, 15 (1) : 281-352. doi: 10.3934/dcds.2006.15.281
[1]

Bin Wang, Arieh Iserles. Dirichlet series for dynamical systems of first-order ordinary differential equations. Discrete & Continuous Dynamical Systems - B, 2014, 19 (1) : 281-298. doi: 10.3934/dcdsb.2014.19.281

[2]

Annalisa Pascarella, Alberto Sorrentino, Cristina Campi, Michele Piana. Particle filtering, beamforming and multiple signal classification for the analysis of magnetoencephalography time series: a comparison of algorithms. Inverse Problems & Imaging, 2010, 4 (1) : 169-190. doi: 10.3934/ipi.2010.4.169

[3]

Xiaoming Wang. Numerical algorithms for stationary statistical properties of dissipative dynamical systems. Discrete & Continuous Dynamical Systems - A, 2016, 36 (8) : 4599-4618. doi: 10.3934/dcds.2016.36.4599

[4]

Marta Štefánková. Inheriting of chaos in uniformly convergent nonautonomous dynamical systems on the interval. Discrete & Continuous Dynamical Systems - A, 2016, 36 (6) : 3435-3443. doi: 10.3934/dcds.2016.36.3435

[5]

Frédéric Naud. The Ruelle spectrum of generic transfer operators. Discrete & Continuous Dynamical Systems - A, 2012, 32 (7) : 2521-2531. doi: 10.3934/dcds.2012.32.2521

[6]

Gary Froyland, Ognjen Stancevic. Escape rates and Perron-Frobenius operators: Open and closed dynamical systems. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 457-472. doi: 10.3934/dcdsb.2010.14.457

[7]

Boris Paneah. Noncommutative dynamical systems with two generators and their applications in analysis. Discrete & Continuous Dynamical Systems - A, 2003, 9 (6) : 1411-1422. doi: 10.3934/dcds.2003.9.1411

[8]

Robert Stephen Cantrell, Suzanne Lenhart, Yuan Lou, Shigui Ruan. Preface on the special issue of Discrete and Continuous Dynamical Systems- Series B in honor of Chris Cosner on the occasion of his 60th birthday. Discrete & Continuous Dynamical Systems - B, 2014, 19 (10) : i-ii. doi: 10.3934/dcdsb.2014.19.1i

[9]

Frédéric Naud. Birkhoff cones, symbolic dynamics and spectrum of transfer operators. Discrete & Continuous Dynamical Systems - A, 2004, 11 (2&3) : 581-598. doi: 10.3934/dcds.2004.11.581

[10]

Damien Thomine. A spectral gap for transfer operators of piecewise expanding maps. Discrete & Continuous Dynamical Systems - A, 2011, 30 (3) : 917-944. doi: 10.3934/dcds.2011.30.917

[11]

Vesselin Petkov, Luchezar Stoyanov. Ruelle transfer operators with two complex parameters and applications. Discrete & Continuous Dynamical Systems - A, 2016, 36 (11) : 6413-6451. doi: 10.3934/dcds.2016077

[12]

Matthew M. Dunlop, Andrew M. Stuart. The Bayesian formulation of EIT: Analysis and algorithms. Inverse Problems & Imaging, 2016, 10 (4) : 1007-1036. doi: 10.3934/ipi.2016030

[13]

Oktay Veliev. Spectral expansion series with parenthesis for the nonself-adjoint periodic differential operators. Communications on Pure & Applied Analysis, 2019, 18 (1) : 397-424. doi: 10.3934/cpaa.2019020

[14]

Isabeau Birindelli, Francoise Demengel. The dirichlet problem for singluar fully nonlinear operators. Conference Publications, 2007, 2007 (Special) : 110-121. doi: 10.3934/proc.2007.2007.110

[15]

Mark F. Demers, Hong-Kun Zhang. Spectral analysis of the transfer operator for the Lorentz gas. Journal of Modern Dynamics, 2011, 5 (4) : 665-709. doi: 10.3934/jmd.2011.5.665

[16]

Gary Froyland, Cecilia González-Tokman, Anthony Quas. Detecting isolated spectrum of transfer and Koopman operators with Fourier analytic tools. Journal of Computational Dynamics, 2014, 1 (2) : 249-278. doi: 10.3934/jcd.2014.1.249

[17]

Doug Hensley. Continued fractions, Cantor sets, Hausdorff dimension, and transfer operators and their analytic extension. Discrete & Continuous Dynamical Systems - A, 2012, 32 (7) : 2417-2436. doi: 10.3934/dcds.2012.32.2417

[18]

Dong Han Kim. The dynamical Borel-Cantelli lemma for interval maps. Discrete & Continuous Dynamical Systems - A, 2007, 17 (4) : 891-900. doi: 10.3934/dcds.2007.17.891

[19]

Hooton Edward, Balanov Zalman, Krawcewicz Wieslaw, Rachinskii Dmitrii. Sliding Hopf bifurcation in interval systems. Discrete & Continuous Dynamical Systems - A, 2017, 37 (7) : 3545-3566. doi: 10.3934/dcds.2017152

[20]

Lassi Roininen, Markku S. Lehtinen. Perfect pulse-compression coding via ARMA algorithms and unimodular transfer functions. Inverse Problems & Imaging, 2013, 7 (2) : 649-661. doi: 10.3934/ipi.2013.7.649

2018 Impact Factor: 1.143

Metrics

  • PDF downloads (9)
  • HTML views (0)
  • Cited by (9)

Other articles
by authors

[Back to Top]