Just now I do not find Rollo Silver’s GCD Algorithm on the web. I thought it was pretty well known but these days it is not know unless it is on the web. This is a remarkable algorithm for it is an improvement on arguably the oldest mathematical algorithm; Euclid described how to find the GCD of two natural numbers, but he used division.

Since numbers are naturally binary, dividing even numbers by two does not count as division. Count the number of zeros at the right of both numbers. Call the minimum of these counts R. Shift both numbers right R bits. (The answer is 2R times the GCD of the two new numbers.) If one of the numbers is even shift it right until it is odd. This does not change the GCD of the two. We have two odd numbers and we repeat the following:

This is a C version.

The number of steps is somewhat larger than for Euclid’s algorithm, but subtracting and shifting are much faster than division. Perhaps I learned this from Knuth’s Semi-Numerical Algorithms where he considers the performance of this algorithm.