×

zbMATH — the first resource for mathematics

Regularity of the Euclid algorithm; application to the analysis of fast GCD algorithms. (English) Zbl 1179.11049
Authors’ summary: 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 \(\varTheta (\mu(n)\log n)\), with a precise remainder term, and estimates of the constant in the \(\varTheta \)-term. Our analysis applies to any cases when the cost \(\mu(n)\) is of order \(\varOmega (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 M. Fürer [Faster integer multiplication. In: Proceedings of STOC’07, 57–66 (2007; Zbl 1179.68198)]. 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 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 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.

MSC:
11Y16 Number-theoretic algorithms; complexity
37C30 Functional analytic techniques in dynamical systems; zeta functions, (Ruelle-Frobenius) transfer operators, etc.
68W40 Analysis of algorithms
Software:
CALYPSO
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baladi, V.; Vallée, B., Exponential decay of correlations for surface semi-flows without finite Markov partitions, Proceedings of the American mathematical society, 133, 3, 865-874, (2004) · Zbl 1055.37027
[2] Baladi, V.; Vallée, B., Euclidean algorithms are Gaussian, Journal of number theory, 110, 2, 331-386, (2005) · Zbl 1114.11092
[3] Brent, R.P., Analysis of the binary Euclidean algorithm, (), 321-355
[4] Cesari, G., 1998. Parallel implementation of Schönhage’s integer GCD algorithm. In: Proceedings of ANTS-III. In: LNCS, vol. 1423. pp. 64-76 · Zbl 0918.11064
[5] Daireaux, B., Maume-Deschamps, V., Vallée, B., 2005. The Lyapounov Tortoise and the dyadic hare. Discrete mathematics and theoretical computer science 2005, In: Proceedings of AofA’05, pp. 71-94 · Zbl 1097.11060
[6] Daireaux, B.; Vallée, B., Dynamical analysis of the parameterized lehmer – euclid algorithm, Combinatorics, probability, computing, 499-536, (2004) · Zbl 1074.11066
[7] Dixon, J.D., The number of steps in the Euclidean algorithm, Journal of number theory, 2, 414-422, (1970) · Zbl 0206.33502
[8] Dolgopyat, D., On decay of correlations in Anosov flows, Annals of mathematics, 147, 357-390, (1998) · Zbl 0911.58029
[9] Efrat, I., Dynamics of the continued fraction map and the spectral theory of \(S L(2, \mathbb{Z})\), Inventiones mathematicae, 114, 207-218, (1993) · Zbl 0811.11037
[10] Ellison, W.; Ellison, F., Prime numbers, (1985), Hermann Paris · Zbl 0624.10001
[11] Flajolet, P., Sedgewick, R., 2008. Analytic Combinatorics, Cambridge University Press (in press) · Zbl 1165.05001
[12] Fürer, M., 2007. Faster integer multiplication. In: Proceedings of STOC’07, pp. 57-66
[13] Heilbronn, H., On the average length of a class of continued fractions, (), 87-96 · Zbl 0212.06503
[14] Hensley, D., The number of steps in the Euclidean algorithm, Journal of number theory, 49, 2, 142-182, (1994) · Zbl 0811.11055
[15] Hwang, H.-K., On convergence rates in the central limit theorems for combinatorial structures, European journal of combinatorics, 19, 329-343, (1998) · Zbl 0906.60024
[16] Jebelean, T., 1997. Practical integer division with Karatsuba complexity. In: Proceedings of ISSAC’97 · Zbl 0923.68072
[17] Jebelean, T., A double-digit lehmer – euclid algorithm for finding the GCD of long integers, Journal of symbolic computation, 19, 145-157, (1995) · Zbl 0832.11046
[18] Knuth, D.E., The art of computer programming, vol. 2, (1998), Addison Wesley Reading, MA · Zbl 0191.17903
[19] Knuth, D.E., (), 269-274
[20] Lehmer, D.H., Euclid’s algorithm for large numbers, The American mathematical monthly, 45, 227-233, (1938) · Zbl 0018.29204
[21] Lhote, L.; Vallée, B., Gaussian laws for the main parameters of the euclid algorithm, Algorithmica, 50, 497-554, (2008), Extended version of Lhote and Vallée (2006) · Zbl 1142.11085
[22] Lhote, L., Vallée, B., 2006. Sharp estimates for the main parameters of the Euclid algorithm. In: Proceedings of LATIN’06. In: LNCS, vol. 3887, pp. 689-702 · Zbl 1143.11364
[23] Mayer, D., A thermodynamic approach to selberg’s zeta function for \(P S L(2, \mathbb{Z})\), Bulletin of American mathematical society, 25, 1, 55-70, (1991)
[24] Möller, N., On schönhage’s algorithm and subquadratic integer gcd computation, Mathematics of computation, 77, 261, 589-607, (January 2008)
[25] Ruelle, D., Thermodynamic formalism, (1978), Addison Wesley
[26] Schönhage, A., Schnelle berechnung von kettenbruchentwicklungen, Acta informatica, 139-144, (1971) · Zbl 0223.68008
[27] Stehlé, D.; Zimmermann, P., A binary recursive gcd algorithm, (), 411-425 · Zbl 1125.11362
[28] Vallée, B., Digits and continuants in euclidean algorithms. ergodic versus Tauberian theorems, Journal de théorie des nombres de Bordeaux, 12, 531-570, (2000) · Zbl 0973.11079
[29] Vallée, B., Dynamical analysis of a class of Euclidean algorithms, Theoretical computer science, 297/1-3, 447-486, (2003) · Zbl 1044.68164
[30] Vallée, B., Euclidean dynamics, Discrete and continuous dynamical systems, 15, 1, 281-352, (May 2006)
[31] Yap, C.K., Fundamental problems in algorithmic algebra, (1996), Princeton University Press
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.