Blanc SIMI 2 - Blanc - SIMI 2 - Science informatique et applications

Dynamics of gcd algorithms: an Algorithmic, Analytic, Arithmetic, and Symbolic approach – DynA3S

Dynamics of gcd algorithms: an Algorithmic, Analytic, Arithmetic, and Symbolic approach

This project aims at studying gcd (greatest common divisor) algorithms from an extended dynamical perspective. It views a gcd algorithm as a dynamical system and focuses on its integer inputs. We are first interested in the algorithmic problem of computing the gcd of several integers, but a further motivation also comes from discrete geometry where the understanding of the most basic primitives, namely discrete lines and planes, relies on algorithms of Euclid type.

Dynamics of gcd algorithms

The computation of the gcd is one of the most basic operations in computational number theory. If the (fast) computation of the gcd of two integers has been widely explored, the situation is more contrasted when considering at least three entries. The computation of the gcd is the main problem we want to tackle with an extensive dynamical approach. <br /> <br />Indeed, dynamical systems have now proved their relevance in computer science, both for their modelling power, and for their efficiency in the analysis of arithmetic algorithms, typically of Euclid type. Indeed, finding a description of an algorithm in terms of a dynamical system enables a deep and precise understanding of the probabilistic behavior of its parameters. A striking example is provided by the Euclid algorithm, the father of all algorithms according to Knuth, associated with the Gauss dynamical system provided by the Gauss map of continued fractions. <br /> <br />We have two main objectives. First, we undertake an extensive study of gcd algorithms which possess an underlying dynamical system. We plan to design efficient gcd algorithms, to perform a systematic analysis (worst-case, average-case and distributional analysis), and to compare the performances of these various algorithms according to a transverse viewpoint combining an algorithmic, analytic, arithmetic and symbolic approach. <br /> <br />Second, we apply these algorithms in discrete geometry for the study of discrete lines and planes, which will provide a further viewpoint on the comparisons between these algorithms. <br /> <br />We will focus here on two types of gcd algorithms, all of them being associated with piecewise linear fractional transformations. The first family relies on lattice reduction algorithms which compute short vectors, whereas the second family gathers multidimensional continued fraction algorithms which compute good rational approximations (such as the Jacobi-Perron algorithm).

We will compare in a systematic way these algorithms and describe their main parameters when inputs are either real (yielding generic trajectories) or integer (yielding truncated trajectories). We simultaneously undertake this study with two different points of views, namely a discrete one, corresponding to rational inputs, and a continuous one, corresponding to real inputs. This gives rise to two dynamical frameworks; which are considered per se, but also in their interaction, within the dynamical analysis methodology.

This methodology mixes tools issued from ergodic theory and symbolic dynamics with tools from analytic combinatorics and algorithmics, and is made of three main steps.
First, the (discrete) algorithm is extended into a continuous dynamical system, where executions of the algorithm are described by particular trajectories, i.e., trajectories of rational points. Second, the main parameters of the algorithm are extended and studied in this continuous framework: the study of particular trajectories is replaced by the study of generic trajectories. Finally, one operates a transfer from continuous to discrete, where it is possible to prove that the probabilistic behavior of the discrete version of the algorithm (related to rational trajectories) is quite similar to the behavior of their continuous counterparts, related to generic trajectories.

Our project thus aims at establishing tight connections between researchers who work in these various domains, and have not yet worked together; inside this project, they all will work on the same object -- study of Euclid type algorithms- - according to different and complementary approaches: dynamical systems with various viewpoints (ergodic, symbolic, real dynamical systems), lattice reduction algorithmics, computer arithmetics, analysis of algorithms, and discrete geometry.

x

x

x

This project aims at studying gcd (greatest common divisor) algorithms from an extended dynamical perspective. It views a gcd algorithm as a dynamical system and focuses on its integer inputs. We are first interested in the algorithmic problem of computing the gcd of several integers. But a further motivation also comes from discrete geometry where the understanding of the most basic primitives, namely discrete lines and planes, relies on algorithms of Euclid type. This viewpoint directed by such an application is an important objective and feature of the project.

We have two main objectives.
- First, we undertake an extensive study of gcd algorithms which possess an underlying dynamical system. We plan to design efficient gcd algorithms, to perform a systematic analysis (worst-case, average-case and distributional analysis), and to compare the performances of these various algorithms according to a transverse viewpoint combining an algorithmic, analytic, arithmetic and symbolic approach.
-Second, we apply these algorithms in discrete geometry for the study of discrete lines and planes, which will provide a further viewpoint on the comparisons between these algorithms.

We will focus here on two types of gcd algorithms, all of them being associated with piecewise linear fractional transformations. The first family relies on lattice reduction algorithms which compute short vectors, whereas the second family gathers multidimensional continued fraction algorithms which compute good rational approximations (such as the Jacobi-Perron algorithm).

We will compare in a systematic way these algorithms and describe their main parameters when inputs are either real (yielding generic trajectories) or integer (yielding truncated trajectories). We simultaneously undertake this study with two different points of views, namely a discrete one, corresponding to rational inputs, and a continuous one, corresponding to real inputs. This gives rise to two dynamical frameworks; which are considered per se, but also in their interaction, within the dynamical analysis methodology. This methodology mixes tools issued from ergodic theory and symbolic dynamics with tools from analytic combinatorics and algorithmics, and is made of three main steps.
-First, the (discrete) algorithm is extended into a continuous dynamical system, where executions of the algorithm are described by particular trajectories, i.e., trajectories of rational points.
-Second, the main parameters of the algorithm are extended and studied in this continuous framework: the study of particular trajectories is replaced by the study of generic trajectories.
-Finally, one operates a transfer from continuous to discrete, where it is possible to prove that the probabilistic behavior of the discrete version of the algorithm (related to rational trajectories) is quite similar to the behavior of their continuous counterparts, related to generic trajectories.

Our project thus aims at establishing tight connections between researchers who work in these various domains, and have not yet worked together; inside this project, they all will work on the same object -- study of Euclid type algorithms-- according to different and complementary approaches: dynamical systems with various viewpoints (ergodic, symbolic, real dynamical systems), lattice reduction algorithmics, computer arithmetics, and analysis of algorithms.

This four-year project gathers 16 permanent researchers, both in theoretical computer science and mathematics, 1 postdoc and 1 PhD Student, for a total of 320 person.months. Two postdoc are also asked for (36 months).

Project coordinator

Madame Valérie BERTHE (INSTITUT DE RECHERCHE EN INFORMATIQUE FONDAMENTALE)

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.

Partner

GREYC Groupe de recherche en informatique, image, automatique et instrumentation de Caen
IRIF INSTITUT DE RECHERCHE EN INFORMATIQUE FONDAMENTALE

Help of the ANR 264,815 euros
Beginning and duration of the scientific project: October 2013 - 48 Months

Useful links