Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)
Abstract
Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)
KTH/SU Mathematics Colloquium
08-05-15
Niels Möller, KTH
Subquadratic GCD
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 talk 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.