Extending Stein’s GCD algorithm and a comparison to Euclid’s GCD algorithm
Summary
Euclid’s algorithm and Stein’s binary GCD algorithm are the two most well-known GCD algorithms. It has already been proven that Euclid’s algorithm is O(n^2), but we aim to provide a more intuitive and thorough proof using an in-depth look at the cost of the modulo operation. An extended version of Stein’s algorithm is also provided with proof of correctness. While there exist other extended versions of Stein’s algorithm, this version distinguishes itself through its relative simplicity and elegant use of properties of Bézout’s identity. Finally, a comparison of the performance of both algorithms with their extended versions is provided.