Самый быстрый алгоритм Евклида вычисления НОД - C (СИ)

Формулировка задачи:

Заинтересовал вопрос о различных реализациях алгоритма Евклида для неотрицательных целых чисел. Ниже привожу алгоритмы, собственноручно написанные, исходя из теоретического материала. Каждый алгоритм можно модифицировать в ту или иную сторону. Считается, что бинарный алгоритм работает быстрее, но мои тесты показывают, что два первых алгоритма работают быстрее бинарного. Может ли кто перепроверить на скорость на своих компиляторах, а то очень интересно и не видится никаких преимуществ бинарного алгоритма.

                    Листинг программы
                
 
                        
                          
                    
//обычный алгоритм Евклида через остатки
long Nod(long a, long b)
{
    while (a && b)
        if (a >= b)
           a %= b;
        else
           b %= a;
    return a | b;
}

                    Листинг программы
                
 
                        
                          
                    
// Алгоритм Евклида через разности
long Nod(long a, long b)
{
    while (a && b)
        if (a >= b)
           a -= b;
        else
           b -= a;
    return a | b;
}

                    Листинг программы
                
 
                        
                          
                    
// Бинарный алгоритм Евклида
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);
}

Еще один бинарный алгоритм, но он самый медленный из всех предыдущих.

                    Листинг программы
                
 
                        
                          
                    
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);
}

Решение задачи: «Самый быстрый алгоритм Евклида вычисления НОД»

Листинг программы

#include <iostream>
 
template <int x, int y>
struct gcd
{
private:
  const static int _value1 = y,
                   _value2 = x % y;
  typedef gcd<static_cast<int>(_value1),
              static_cast<int>(_value2)>
              next_step_type;
 
public:
  const static int value = next_step_type::value;
};
 
template <int x>
struct gcd<x, 0>
{
  const static int value = x;
};
 
int main(){
  std::cout << gcd<2344, 5432>::value << std::endl;
  return 0;
}

Объяснение кода листинга программы

В данном коде представлен самый быстрый алгоритм Евклида вычисления НОД (наибольшего общего делителя) двух целых чисел. Алгоритм основан на рекурсивном применении евклидова алгоритма к остатку от деления.

В первой строке объявляется шаблон структуры gcd, который принимает два целых числа x и y в качестве параметров.
В блоке private структуры gcd объявляются две константы _value1 и _value2, которые инициализируются значениями y и x % y соответственно. % - это оператор взятия остатка от деления.
Далее, используя оператор static_cast, мы приводим значения _value1 и _value2 к типу int для обеспечения корректной работы алгоритма.
Затем мы определяем новый шаблон next_step_type, который будет использоваться в рекурсивном вызове функции gcd.
В блоке public структуры gcd объявляется константа value, которая инициализируется значением next_step_type::value, т.е. результатом рекурсивного вызова функции gcd с новыми значениями _value1 и _value2.
В конце кода в функции main выводится значение gcd<2344, 5432>::value на экран.
В структуре gcd также присутствует специальный случай для вычисления НОД двух чисел, когда одно из них равно нулю. В этом случае возвращается второе число. Это сделано для корректной работы алгоритма. Список вызовов функций и значения переменных в данном коде:
gcd<2344, 5432>::value - вызов функции gcd с аргументами 2344 и 5432, результат выводится на экран.