Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


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


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)$.
  • Torbjörn Granlund, GNU multiple precision arithmetic library, version 4.1.4, September 2004,
  • 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
  • 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
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC (2000): 11A05, 11Y16
  • Retrieve articles in all journals with MSC (2000): 11A05, 11Y16
Additional Information
  • Niels Möller
  • Affiliation: Automatic control, KTH, SE-100 44, Sweden
  • Email:
  • 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:
  • MathSciNet review: 2353968