Analysis of a left-shift binary GCD algorithm (Q1338738)

The following algorithm is given for finding the GCD \((u,v)\) where \(u > v > 0\). Let \(e\) be such that \(2^ ev \leq u < 2^{e+1}v\), and let \(t = \min (u - 2^ ev, 2^{e+1} v - u)\). Then replace \(u,v\) by \(v,t\), interchanging and repeating as necessary. Let \(x_ n, y_ n\) be the lexicographically least pair that requires \(n\) iterations: \(x_ n\) and \(y_ n\) are determined explicitly. Some comparisons of a) run time, and b) number of iterations were made for inputs of length 100, 250, 500, and 1000 decimal digits, with 100 pseudo-random numbers used for each length, and with various algorithms. On average the new algorithm was not the best for either a) or b), but it is stated that for extended computation it has been found to be the fastest.