Monthly Archives: October 2018

Implementing the Extended Euclidean Algorithm with Unsigned Inputs

As the previous post showed, it’s possible to correctly implement the Extended Euclidean Algorithm using one signed integral type for all input parameters, intermediate variables, and output variables. None of the calculations will overflow. The implementation was given as follows: … Continue reading

Posted in Uncategorized | 11 Comments

Proof of Bounds for the Extended Euclidean Algorithm

Euclid’s method is a classic algorithm for finding the greatest common divisor (gcd) of two integers. Donald Knuth referred to it as “the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present … Continue reading

Posted in Uncategorized | 4 Comments