Robust HGCD with no backup steps
2006 (English)In: Mathematical Software-ICMS 2006, Proceedings / [ed] Iglesias, A; Takayama, N, 2006, Vol. 4151, 194-204 p.Conference paper (Refereed)
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
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-42008ISI: 000240541100017ScopusID: 2-s2.0-33750077252ISBN: 3-540-38084-1OAI: oai:DiVA.org:kth-42008DiVA: diva2:445881
2nd International Congress on Mathematical Software, ICMS 2006; Castro Urdiales; 1 September 2006 through 3 September 2006
QC 201110052011-10-052011-10-052011-10-05Bibliographically approved