Change search
ReferencesLink to record
Permanent link

Direct link
Robust HGCD with no backup steps
KTH, School of Electrical Engineering (EES), Automatic Control.
2006 (English)In: Mathematical Software-ICMS 2006, Proceedings / [ed] Iglesias, A; Takayama, N, 2006, Vol. 4151, 194-204 p.Conference paper (Refereed)
Abstract [en]

Subquadratic divide-and-conquer algorithms for computing the greatest common divisor have been studied for a couple of decades. The integer case has been notoriously difficult, with the need for "backup steps" in various forms. This paper explains why backup steps are necessary for algorithms based directly on the quotient sequence, and proposes a robustness criterion that can be used to construct a "half-gcd" algorithm without any backup steps.

Place, publisher, year, edition, pages
2006. Vol. 4151, 194-204 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 4151
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-42008ISI: 000240541100017ScopusID: 2-s2.0-33750077252ISBN: 3-540-38084-1OAI: diva2:445881
2nd International Congress on Mathematical Software, ICMS 2006; Castro Urdiales; 1 September 2006 through 3 September 2006
QC 20111005Available from: 2011-10-05 Created: 2011-10-05 Last updated: 2011-10-05Bibliographically approved

Open Access in DiVA

No full text


Search in DiVA

By author/editor
Möller, Niels
By organisation
Automatic Control
Computer and Information Science

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

Total: 12 hits
ReferencesLink to record
Permanent link

Direct link