Заинтересовал вопрос о различных реализациях алгоритма Евклида для неотрицательных целых чисел. Ниже привожу алгоритмы, собственноручно написанные, исходя из теоретического материала. Каждый алгоритм можно модифицировать в ту или иную сторону.
Считается, что бинарный алгоритм работает быстрее, но мои тесты показывают, что два первых алгоритма работают быстрее бинарного. Может ли кто перепроверить на скорость на своих компиляторах, а то очень интересно и не видится никаких преимуществ бинарного алгоритма.
Код C
//обычный алгоритм Евклида через остатки
long Nod(long a, long b)
{
while (a && b)
if (a >= b)
a %= b;
else
b %= a;
return a | b;
}
Код C
// Алгоритм Евклида через разности
long Nod(long a, long b)
{
while (a && b)
if (a >= b)
a -= b;
else
b -= a;
return a | b;
}
Код C
// Бинарный алгоритм Евклида
long Nod(long a, long b)
{
long deg = 0;
if (a == 0 || b == 0)
return a | b;
while (((a | b) & 1) == 0)
{
deg++;
a >>= 1;
b >>= 1;
}
while (a && b)
{
if (b & 1)
while ((a & 1) == 0)
a >>= 1;
else
while ((b & 1) == 0)
b >>= 1;
if (a >= b)
a = (a - b) >> 1;
else
b = (b - a) >> 1;
}
return ((a | b) << deg);
}
Еще один бинарный алгоритм, но он самый медленный из всех предыдущих.
Код C
long Nod(long a, long b)
{
long buf, deg = 0;
if (a == 0 || b == 0)
return a | b;
while (((a | b) & 1) == 0)
{
deg++;
a >>= 1;
b >>= 1;
}
if (a)
while ((a & 1) == 0)
a >>= 1;
while (b)
{
while ((b & 1) == 0)
b >>= 1;
if (a < b)
b -= a;
else
{
buf = a - b;
a = b;
b = buf;
}
b >>= 1;
}
return (a << deg);
}