Бінарний алгоритм пошуку найбільшого спільного дільника

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

Бінарний алгоритм знаходження НСД базується на наступних властивостях:

  • НСД(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();
    }
}

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

Дивіться також: