Mostrar el registro sencillo del ítem
dc.contributor.author
Cesaratto, Eda
dc.contributor.author
Clément, Julien
dc.contributor.author
Daireaux, Benoit
dc.contributor.author
Lhote, Loick
dc.contributor.author
Maume, Veronique
dc.contributor.author
Vallée, Brigitte
dc.date.available
2024-08-13T14:44:48Z
dc.date.issued
2009-07
dc.identifier.citation
Cesaratto, Eda; Clément, Julien; Daireaux, Benoit; Lhote, Loick; Maume, Veronique; et al.; Regularity of the Euclid Algorithm; application to the analysis of fast GCD Algorithms; Academic Press Ltd - Elsevier Science Ltd; Journal Of Symbolic Computation; 44; 7; 7-2009; 726-767
dc.identifier.issn
0747-7171
dc.identifier.uri
http://hdl.handle.net/11336/242416
dc.description.abstract
This paper is an extended complete version of ´´Analysis of fast versions of Euclid Algorithm´´ presented in ANALCO´07. Among the differences here we deal with several Fast multiplication algorithms and we give precise estimates of the constants involved. There exist fast variants of the gcd algorithm which are all based on principles due to Knuth and Schönhage. On inputs of size n, these algorithms use a Divide and Conquer approach, perform FFT multiplications with complexity mu(n) and stop the recursion at a depth slightly smaller than log n. A rough estimate of the worst--case complexity of these fast versions provides the bound O ( mu(n)log n). Even the worst-case estimate is partly based on heuristics and is not actually proven. Here, we provide a precise probabilistic analysis of some of these fast variants, and we prove that their average bit--complexity on random inputs of size n is Theta (mu(n) log n , with a precise remainder term, and estimates of the constant in the Theta--term. Our analysis applies to any cases when the cost mu(n) is of order Omega(n log n), and is valid both for the FFT multiplication algorithm of Schönhage--Stassen, but also for the new algorithm introduced quite recently by Fürer . We view such a fast algorithm as a sequence of what we call interrupted algorithms, and we obtain two main results about the (plain) Euclid Algorithm which are of independent interest. We precisely describe the evolution of the distribution of numbers during the execution of the (plain) Euclid Algorithm, and we exhibit an (unexpected) density psi which plays a central rôle since it always appear at the beginning of each recursive call. This strong regularity phenomenon proves that the interrupted algorithms are locally ``similar´´ to the total algorithm. This finally leads to the precise evaluation of the average bit--complexity of these fast algorithms. This work uses various tools, and is based on a precise study of generalised transfer operators related to the dynamical system underlying the Euclid Algorithm.nhage. On inputs of size n, these algorithms use a Divide and Conquer approach, perform FFT multiplications with complexity mu(n) and stop the recursion at a depth slightly smaller than log n. A rough estimate of the worst--case complexity of these fast versions provides the bound O ( mu(n)log n). Even the worst-case estimate is partly based on heuristics and is not actually proven. Here, we provide a precise probabilistic analysis of some of these fast variants, and we prove that their average bit--complexity on random inputs of size n is Theta (mu(n) log n , with a precise remainder term, and estimates of the constant in the Theta--term. Our analysis applies to any cases when the cost mu(n) is of order Omega(n log n), and is valid both for the FFT multiplication algorithm of Schönhage--Stassen, but also for the new algorithm introduced quite recently by Fürer . We view such a fast algorithm as a sequence of what we call interrupted algorithms, and we obtain two main results about the (plain) Euclid Algorithm which are of independent interest. We precisely describe the evolution of the distribution of numbers during the execution of the (plain) Euclid Algorithm, and we exhibit an (unexpected) density psi which plays a central rôle since it always appear at the beginning of each recursive call. This strong regularity phenomenon proves that the interrupted algorithms are locally ``similar´´ to the total algorithm. This finally leads to the precise evaluation of the average bit--complexity of these fast algorithms. This work uses various tools, and is based on a precise study of generalised transfer operators related to the dynamical system underlying the Euclid Algorithm.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Academic Press Ltd - Elsevier Science Ltd
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
EUCLID ALGORITHMS
dc.subject
DIVIDE AND CONQUER ALGORITHMS
dc.subject
FAST MULTIPLICATION
dc.subject
ANALYSIS OF ALGORITHMS
dc.subject
TRANSFER OPERATORS
dc.subject
PERRON FORMULA
dc.subject.classification
Matemática Aplicada
dc.subject.classification
Matemáticas
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.title
Regularity of the Euclid Algorithm; application to the analysis of fast GCD Algorithms
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2024-08-13T12:32:50Z
dc.journal.volume
44
dc.journal.number
7
dc.journal.pagination
726-767
dc.journal.pais
Estados Unidos
dc.description.fil
Fil: Cesaratto, Eda. Centre National de la Recherche Scientifique; Francia. Universidad Nacional de General Sarmiento. Instituto del Desarrollo Humano; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.description.fil
Fil: Clément, Julien. Centre National de la Recherche Scientifique; Francia
dc.description.fil
Fil: Daireaux, Benoit. No especifíca;
dc.description.fil
Fil: Lhote, Loick. Centre National de la Recherche Scientifique; Francia
dc.description.fil
Fil: Maume, Veronique. Universite Lyon 2; Francia
dc.description.fil
Fil: Vallée, Brigitte. Centre National de la Recherche Scientifique; Francia
dc.journal.title
Journal Of Symbolic Computation
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.jsc.2008.04.018
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0747717108001193
Archivos asociados