On Schönhage’s algorithm and subquadratic integer gcd computation
Niels Christian Møller · Mathematics of Computation · 2007
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 ) O(n (\log n)^ 2 \log \log n) .