Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

   
 
 

 

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


Author: 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
Published electronically: September 12, 2007
MathSciNet review: 2353968
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Torbjörn Granlund, GNU multiple precision arithmetic library, version 4.1.4, September 2004, http://swox.com/gmp.
  • [2] Tudor Jebelean, A double-digit Lehmer-Euclid algorithm for finding the GCD of long integers, Journal of Symbolic Computation 19 (1995), no. 1-3, 145-157. MR 1339115 (96h:11128)
  • [3] Donald E. Knuth, The analysis of algorithms, Actes du Congrés International des Mathématiciens (1970), 269-274. MR 0423865 (54:11839)
  • [4] D. H. Lehmer, Euclid's algorithm for large numbers, American Mathematical Monthly 45 (1938), 227-233. MR 1524250
  • [5] Bradley Lucier, Personal communication, 2005.
  • [6] Victor Y. Pan and Xinmao Wang, Acceleration of Euclidean algorithm and extensions, ISSAC '02: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation (New York, NY, USA), ACM Press, 2002, pp. 207-213. MR 2035251 (2005a:68101)
  • [7] Arnold Schönhage, Schnelle Berechnung von Kettenbruchentwicklungen, Acta Informatica 1 (1971), 139-144.
  • [8] -, 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.
  • [9] Jonathan P. Sorenson, Two fast GCD algorithms, Journal of Algorithms 16 (1994), no. 1, 110-144. MR 1251841 (94k:11135)
  • [10] Damien Stehlé and Paul Zimmermann, A binary recursive GCD algorithm, ANTS-VI (Burlington) (D. Buell, ed.), LCNS, vol. 3076, Springer-Verlag, June 2004. MR 2138011 (2006e:11194)
  • [11] J. Stein, Computational problems associated with Racah algebra, Journal of Computational Physics 1 (1967), no. 3, 397-405.
  • [12] 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.
  • [13] Kenneth Weber, The accelerated integer GCD algorithm, ACM Transactions on Mathematical Software 21 (1995), 111-122. MR 1365811 (96h:68084)
  • [14] André Weilert, Ein schneller algorithmus zur berechnung des quartischen restsymbols, Diplomarbeit, Math. Inst. der Univ., Bonn, 1999.
  • [15] -, Asymptotically fast GCD computation in $ Z[i]$, ANTS-IV: Proc. of Fourth Intern. Symp. Algorithmic Number Theory (Leiden), LNCS, no. 1838, Springer-Verlag, July 2000, pp. 595-613. MR 1850636 (2002k:11226)

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: nisse@lysator.liu.se

DOI: https://doi.org/10.1090/S0025-5718-07-02017-0
Received by editor(s): November 19, 2005
Published electronically: September 12, 2007
Article copyright: © Copyright 2007 Niels Möller

American Mathematical Society