homepage

> A C reimplementation of gcd probably makes little sense -- for large
> numbers it is dominated by the cost of the arithmetic, and that will
> remain the same.
That's true for a direct translation of the usual algorithm. But 
there's a variant due to Lehmer which reduces the number of multi-
precision operations, and dramatically reduces the number of full-
precision divmod operations---they're mostly replaced by n-limb-by-1-
limb multiplications and full-precision additions. I'd expect at least 
a factor of 2 speedup from using this; possibly more. Of course it's 
impossible to tell without implementing it.
I've attached a Python version; note that:
 * the operations to find x and y at the start of the outer while loop 
are simple lookups when written in C
 * the else branch is taken rarely: usually once at the beginning of 
any gcd() calculation, and then less than 1 time in 20000 on average 
during the reduction.
 * all the arithmetic in the inner while loop is done with numbers <= 
2**15 in absolute value.
Mark