Бинарный алгоритм поиска наибольшего общего делителя

Бинарный алгоритм Евклида – это ускоренный алгоритм для поиска наибольшего общего делителя двух чисел.

Бинарный алгоритм нахождения НОД основан на следующих свойствах:

  • НОД(2⋅a, 2⋅b) = 2⋅НОД(a, b);
  • НОД(2⋅a, 2⋅b + 1) = НОД(a, 2⋅b + 1);
  • НОД(-a, b) = НОД(a, b).

Описание алгоритма

  1. НОД(0, b) = b;
  2. НОД(a, 0) = НОД(a, a) = a;
  3. НОД(1, b) = НОД(a, 1) = 1;
  4. Если a и b четные, то НОД(a, b) = 2⋅НОД(a/2, b/2);
  5. Если a четное и b нечетное, то НОД(a, b) = НОД(a/2, b);
  6. Если a нечетное и b четное, то НОД(a, b) = НОД(a, b/2);
  7. Если a и b нечетные:
    • при этом b > a, то НОД(a, b) = НОД((b-a)/2, a);
    • при этом b < a, то НОД(a, b) = НОД((a-b)/2, b).

Рекурсивная реализация алгоритма бинарного поиска наибольшего общего делителя

Поскольку нужно максимально ускорить вычисление, при каждой возможности, будем использовать битовые операции.

Замена арифметических операций битовыми:

  • Умножение на два, заменим на битовое смещение: x * 2 эквивалентно смещению на один бит влево x << 1;
  • Деление на два, также возможно с битовым смещением: x / 2 эквивалентно смещению на бит вправо x >> 1;
  • Проверка на четность: x % 2 == 0, эквивалентно (x & 1) == 0 (у четного числа последний бит равен нулю);
  • Соответственно проверка на нечетность: x % 2 != 0 эквивалентно (x & 1) == 1 (у нечетного числа последний бит равен единице).

Программа для нахождения наибольшего общего делителя с помощью рекурсивного бинарного алгоритма Евклида:

using System;
//класс с методами расширения
public static class UInt32Ext
{
    //число нечетное
    public static bool IsOdd(this uint num) => (num & 1) == 1;

    //число четное
    public static bool IsEven(this uint num) => (num & 1) == 0;

    //быстрое умножение на два
    public static uint Mul2(this uint n) => n << 1;

    //быстрое деление на два
    public static uint Div2(this uint n) => n >> 1;
}

class Program
{
    static uint BinaryGCD(uint a, uint b)
    {
        if (a == b || a == 0)
            return b;

        if (b == 0)
            return a;

        if (a.IsEven())
        {
            return b.IsOdd() 
                ? BinaryGCD(a.Div2(), b) 
                : BinaryGCD(a.Div2(), b.Div2()).Mul2();
        }
        else if (b.IsEven())
        {
            return BinaryGCD(a, b.Div2());
        }
        else
        {
            return a > b 
                ? BinaryGCD((a - b).Div2(), b) 
                : BinaryGCD((b - a).Div2(), a);
        }
    }

    static void Main(string[] args)
    {
        Console.WriteLine("Бинарный алгоритм Евклида");
        Console.Write("A = ");
        var x1 = Convert.ToUInt32(Console.ReadLine());
        Console.Write("B = ");
        var x2 = Convert.ToUInt32(Console.ReadLine());
        Console.WriteLine("Наибольший общий делитель чисел {0} и {1} равен {2}", x1, x2, BinaryGCD(x1, x2));
        Console.ReadLine();
    }
}

Результат работы программы:

Смотрите также: