Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 4151
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-42008ISI: 000240541100017Scopus ID: 2-s2.0-33750077252ISBN: 3-540-38084-1 (print)OAI: oai:DiVA.org:kth-42008DiVA: diva2:445881
Conference
2nd International Congress on Mathematical Software, ICMS 2006; Castro Urdiales; 1 September 2006 through 3 September 2006
Note
QC 20111005Available from: 2011-10-05 Created: 2011-10-05 Last updated: 2011-10-05Bibliographically approved

Open Access in DiVA

No full text

Scopus

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 22 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf