Change search
ReferencesLink to record
Permanent link

Direct link
On Schonhage's algorithm and subquadratic integer GCD computation
KTH, School of Electrical Engineering (EES), Automatic Control.
2008 (English)In: Mathematics of Computation, ISSN 0025-5718, E-ISSN 1088-6842, Vol. 77, no 261, 589-607 p.Article in journal (Refereed) Published
Abstract [en]

We describe a new subquadratic left-to-right GCD algorithm, inspired by Schonhage's algorithm for reduction of binary quadratic forms, and compare it to the first subquadratic GCD algorithm discovered by Knuth and Schonhage, and to the binary recursive GCD algorithm of Stehle and Zimmer-mann. 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).

Place, publisher, year, edition, pages
2008. Vol. 77, no 261, 589-607 p.
National Category
Computational Mathematics
URN: urn:nbn:se:kth:diva-36407DOI: 10.1090/S0025-5718-07-02017-0ISI: 000251537000029ScopusID: 2-s2.0-38849115715OAI: diva2:430675

QC 20141029

Available from: 2011-07-12 Created: 2011-07-12 Last updated: 2014-10-29Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Möller, Niels
By organisation
Automatic Control
In the same journal
Mathematics of Computation
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 27 hits
ReferencesLink to record
Permanent link

Direct link