Frage zu Laufzeit von algorithmus (GCD)

[BigO?]

Hallo, ich wollte für meine Zahlenklasse einen Greatest Common Divisor Algorithmus implementieren. Auf Wikipedia habe ich diesen Code gefunden (etwas abgeändert):

void binary_gcd(T u, T v, T& res)
{
	if (u == 0 || v == 0)
	{
		res = u | v;
		return;
	}

	unsigned int shift = 0;

	for (; ((u | v) & 1) == 0; ++shift)
	{
		u >>= 1;
		v >>= 1;
	}

	while ((u & 1) == 0)
		u >>= 1;

	T tmp;
	do
	{
		while ((v & 1) == 0)
			v >>= 1;

		if (u < v)
			v -= u;
		else
		{
			tmp = u - v;
			u = v;
			v = tmp;
		}

		v >>= 1;
	} while (v);

	res = u << shift;
}

Dabei ist T meine Zahlenklasse.
In der Boost Doku habe ich diesen Algorithmus gefunden:

void binary_gcd(T n, T m, T& res)
{  

	if( n == 0 || m == 0)
	{
		res = n | m;
		return;
	}

	nrs mOdds = 0;
	nrs nOdds = 0;

	for( ; (m & 1) == 0 ; m >>= 1, mOdds++ );
	for( ; (n & 1) == 0 ; n >>= 1, nOdds++ );

	for( ; n != m ; )
	{
		if( n < m )
		{
			for( m -= n, m >>= 1; (m & 1) == 0 ; m >>= 1 );
		}
		else
		{
			for( n -= m, n >>= 1; (n & 1) == 0 ; n >>= 1 );
		}
	}

	res = m << min( mOdds, nOdds );
}

Der zweite Algorithmus läuft bei mir ungefähr doppelt so schnell, wie der erste. Der einzige Unterschied, der mir auffällt, ist, dass ich im Ersten eine zusätzliche temporäre Variable brauche. Allerdings kann ich mir nicht vorstellen, dass das viel an der Geschwindigkeit ändert (es ist ein statisches array, das mit memcpy gefüllt wird).
Kann sich jemand von euch vorstellen, warum die zweite Variante doppelt so schnell ist wie die Erste?

[BigO?]

edit: mOdds und nOdds sind vom typ unsigned int !