The Euclidean algorithm computes the $\gcd$ of two integers with the recursive formula
and takes at worst $\log_\varphi(\min(a,b))$ steps, where $\varphi$ is the golden ratio.
What if instead one used
whenever $a\bmod b$ was greater than $b/2$?
It is easy to see this will take at worst no more than $\log_2(\min(a,b))$ steps since this ensures the second argument is at most half of the first argument, but what is the exact worst case constant coeefficient?
The only sequence of pairs of integers I've managed to get the exact behavior of are consecutive Fibonacci numbers, in which case this modified algorithm runs twice as fast as the usual, which is faster than the $\log_2$ bound.
Here is a program displaying the values on each step of the standard Euclidean algorithm and the above modification.