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

2018/08/23 by Grenet, Bruno, Volkovich, Ilya
#68Q25 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1808.07957

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.

Related

• Euclidean algorithms are Gaussian
• The Accelerated Euclidean Algorithm
• The k-Dimensional Weisfeiler-Leman Algorithm
• A rigorous version of R. P. Brent's model for the binary Euclidean algorithm
• A One-Way Function Based On The Extended Euclidean Algorithm