The Brun gcd algorithm in high dimensions is almost always subtractive. (March 2018)

• Record Type: Journal Article
• Authors: Berthé, Valérie; Lhote, Loïck; Vallée, Brigitte
• Is Part Of: Journal of symbolic computation. Volume 85(2018)
• Page Start: 72
• Page End: 107
• Publication Date: 2018-03
• Subjects: Multiple GCD algorithm -- Multidimensional continued fraction -- Analytic combinatorics -- Dirichlet generating functions -- Average-case analysis -- Transfer operator -- Dynamical analysis -- Tauberian Theorem; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2017.07.004
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: We introduce and study an algorithm which computes the gcd of d + 1 entries. This is a natural extension of the usual Euclid algorithm, and coincides with it for d = 1 ; it performs Euclidean divisions, between the largest entry and the second largest entry, and then re-orderings. This is the discrete version of a multidimensional continued fraction algorithm due to Brun, in d dimensions. We perform the average-case analysis of this algorithm, and prove that the mean number of steps is linear with respect to the size of the entry. The method is based on the study of the underlying Brun dynamical system, and relies on dynamical analysis. All the constants that arise in the analysis are mathematical constants which are defined via the Brun dynamical system: for instance, the main constant of the analysis involves the entropy of the system, and the other constants of the analysis are related to fine properties of the invariant measure of the system. We are then led to the asymptotic behaviour of the Brun dynamical system, when dimension d becomes large, which is of independent interest. We show that the asymptotic Brun dynamical system almost always involves quotients that are equal to 1, and is then almost always subtractive. This explains the inefficiency of the Brun gcd algorithm, particularly when it is compared in high dimensions to another extension of the Euclid algorithm, proposed by Knuth, and already analyzed by the authors.