Résumé
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.
- Titre
- One (more) line on the most Ancient Algorithm in History
- Créateurs - sans rôle
- Bruno Grenet - Exact Dynamics (Netherlands)Ilya Volkovich - University of Michigan
- Colloque
- SOSA 2020 - 1st Symposium on Simplicity in Algorithms (Salt Lake City, United States, 06/01/2020–07/01/2020)
- Identifiants
- 99151664909311
- Unité académique
- Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier - LIRMM
- Langue
- English
- Type de ressource
- Conference proceeding
- Champs locaux
- lirmm-02335368