> 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