On Schönhage’s algorithm and subquadratic integer gcd computation

Möller, Niels

doi:10.1090/S0025-5718-07-02017-0

On Schönhage’s algorithm and subquadratic integer gcd computation
HTML articles powered by AMS MathViewer

by Niels Möller PDF

Math. Comp. 77 (2008), 589-607

Abstract:

We describe a new subquadratic left-to-right gcd algorithm, inspired by Schönhage’s algorithm for reduction of binary quadratic forms, and compare it to the first subquadratic gcd algorithm discovered by Knuth and Schönhage, and to the binary recursive gcd algorithm of Stehlé and Zimmermann. The new gcd algorithm runs slightly faster than earlier algorithms, and it is much simpler to implement. The key idea is to use a stop condition for hgcd that is based not on the size of the remainders, but on the size of the next difference. This subtle change is sufficient to eliminate the back-up steps that are necessary in all previous subquadratic left-to-right gcd algorithms. The subquadratic gcd algorithms all have the same asymptotic running time, $O(n (\log n)^ 2 \log \log n)$.

References

Torbjörn Granlund, GNU multiple precision arithmetic library, version 4.1.4, September 2004, http://swox.com/gmp.
Tudor Jebelean, A double-digit Lehmer-Euclid algorithm for finding the GCD of long integers, J. Symbolic Comput. 19 (1995), no. 1-3, 145–157. Design and implementation of symbolic computation systems (Gmunden, 1993). MR 1339115, DOI 10.1006/jsco.1995.1009
Donald E. Knuth, The analysis of algorithms, Actes du Congrès International des Mathématiciens (Nice, 1970) Gauthier-Villars, Paris, 1971, pp. 269–274. MR 0423865
D. H. Lehmer, Euclid’s Algorithm for Large Numbers, Amer. Math. Monthly 45 (1938), no. 4, 227–233. MR 1524250, DOI 10.2307/2302607
Bradley Lucier, Personal communication, 2005.
Victor Y. Pan and Xinmao Wang, Acceleration of Euclidean algorithm and extensions, Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2002, pp. 207–213. MR 2035251, DOI 10.1145/780506.780533
Arnold Schönhage, Schnelle Berechnung von Kettenbruchentwicklungen, Acta Informatica 1 (1971), 139–144.
—, Fast reduction and composition of binary quadratic forms, Proc. of Intern. Symp. on Symbolic and Algebraic Computation (Bonn) (S. M. Watt, ed.), ACM Press, 1991, pp. 128–133.
Jonathan Sorenson, Two fast GCD algorithms, J. Algorithms 16 (1994), no. 1, 110–144. MR 1251841, DOI 10.1006/jagm.1994.1006
Damien Stehlé and Paul Zimmermann, A binary recursive gcd algorithm, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 3076, Springer, Berlin, 2004, pp. 411–425. MR 2138011, DOI 10.1007/978-3-540-24847-7_{3}1
J. Stein, Computational problems associated with Racah algebra, Journal of Computational Physics 1 (1967), no. 3, 397–405.
Klaus Thull and Chee K. Yap, A unified approach to HGCD algorithms for polynomials and integers, 1990, Manuscript. Available from http://cs.nyu.edu/cs/faculty/yap/papers.
Kenneth Weber, The accelerated integer GCD algorithm, ACM Trans. Math. Software 21 (1995), no. 1, 111–122. MR 1365811, DOI 10.1145/200979.201042
André Weilert, Ein schneller algorithmus zur berechnung des quartischen restsymbols, Diplomarbeit, Math. Inst. der Univ., Bonn, 1999.
André Weilert, Asymptotically fast GCD computation in $\Bbb Z[i]$, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 595–613. MR 1850636, DOI 10.1007/10722028_{4}0