Details:
Title  Regularity of the Euclid Algorithm; application to the analysis of fast GCD Algorithms  Author(s)  Eda Cesaratto, Julien Clément, Benoît Daireaux, Loïck Lhote, Véronique MaumeDeschamps, Brigitte Vallée  Type  Article in Journal  Abstract  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 μ ( n ) and stop the recursion at a depth slightly smaller than lg n . A rough estimate of the worstcase complexity of these fast versions provides the bound O ( μ ( n ) log n ) . Even the worstcase 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 bitcomplexity on random inputs of size n is Θ ( μ ( n ) log n ) , with a precise remainder term, and estimates of the constant in the Θ term. Our analysis applies to any cases when the cost μ ( n ) is of order Ω ( n log n ) , and is valid both for the FFT multiplication algorithm of Schönhage–Strassen, but also for the new algorithm introduced quite recently by Fürer [Fürer, M., 2007. Faster integer Multiplication. In: Proceedings of STOC’07. pp. 57–66]. 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 ψ which plays a central rôle since it always appears at the beginning of each recursive call. This strong regularity phenomenon proves that the interrupted algorithms are locally “similar” to the total algorithm. This ultimately leads to the precise evaluation of the average bitcomplexity 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.  Keywords  Euclid algorithm, Divide and conquer algorithms, Fast multiplication, Analysis of algorithms, Transfer operators, Perron formula  ISSN  07477171 
URL 
http://www.sciencedirect.com/science/article/pii/S0747717108001193 
Language  English  Journal  Journal of Symbolic Computation  Volume  44  Number  7  Pages  726  767  Year  2009  Note  International Symposium on Symbolic and Algebraic Computation  Edition  0  Translation 
No  Refereed 
No 
