One (more) line on the most Ancient Algorithm in History - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2020

One (more) line on the most Ancient Algorithm in History

Bruno Grenet
Exact Computing
CV
Ilya Volkovich
  • Function : Author
  • PersonId : 1057054
University of Michigan [Ann Arbor]

Abstract

We give a new simple and short ("one-line") analysis for the runtime of the well-known Euclidean Algorithm. While very short simple, the obtained upper bound in near-optimal.

Domains

Computational Complexity [cs.CC] Symbolic Computation [cs.SC]
Fichier principal
Vignette du fichier
hal.pdf (81 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Bruno Grenet  : Connect in order to contact the contributor

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02335368

Submitted on : Monday, October 28, 2019-11:34:55 AM

Last modification on : Tuesday, October 3, 2023-11:32:49 AM

Long-term archiving on : Wednesday, January 29, 2020-2:09:41 PM

Download

Dates and versions

lirmm-02335368 , version 1 (28-10-2019)

Identifiers

Cite

Bruno Grenet, Ilya Volkovich. One (more) line on the most Ancient Algorithm in History. SOSA 2020 - 1st Symposium on Simplicity in Algorithms, Jan 2020, Salt Lake City, United States. ⟨10.1137/1.9781611976014.3⟩. ⟨lirmm-02335368⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

CNRS ECO LIRMM MIPS UNIV-MONTPELLIER
142 View
945 Download

Altmetric

Share

More