On Schönhage’s algorithm and subquadratic integer gcd computation
HTML articles powered by AMS MathViewer
- by Niels Möller;
- Math. Comp. 77 (2008), 589-607
- DOI: https://doi.org/10.1090/S0025-5718-07-02017-0
- Published electronically: September 12, 2007
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 Éditeur, Paris, 1971, pp. 269–274. MR 423865
- 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
Bibliographic Information
- Niels Möller
- Affiliation: Automatic control, KTH, SE-100 44, Sweden
- Email: nisse@lysator.liu.se
- Received by editor(s): November 19, 2005
- Published electronically: September 12, 2007
- © Copyright 2007 Niels Möller
- Journal: Math. Comp. 77 (2008), 589-607
- MSC (2000): Primary 11A05, 11Y16
- DOI: https://doi.org/10.1090/S0025-5718-07-02017-0
- MathSciNet review: 2353968