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

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?)

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

Received by editor(s): November 19, 2005
Published electronically: September 12, 2007
Article copyright: © Copyright 2007 Niels Möller