> Why are the two Py_ABS() calls at the end needed when we start off the
> algorithm with long_abs()?

Because long_abs()'s are omitted for small enough numbers (common case). So we 
avoid a copying for negative numbers or int subclasses.

> I guess that's why you added the pure Euclidean implementation

Euclidean algorithm is required step at the end of Lehmer algorithm.

> It's 4% faster than the Euclidean code for the fractions benchmark
> when using 30 bit digits, but (surprisingly enough) about the same speed
> with 15 bit digits.

May be because Lehmer code uses 64-bit computation for 30-bit digits, and 
Euclidean code always uses 32-bit computation.

> The difference for big numbers is substantial though:

1000-bit integers are big, but can be encountered in real word (e.g. in 
cryptography). So may be there is need in Lehmer algorithm.