Рубрики

Алгоритм Евклида, когда% и / операции являются дорогостоящими

Алгоритм Евклида используется, чтобы найти GCD двух чисел.

Есть в основном две версии алгоритма.
Версия 1 (с использованием вычитания)

// Рекурсивная функция для возврата gcd из a и b

int gcd(int a, int b)

{

    if (a == b)  

       return a;

   

    return (a > b)? gcd(a-b, b): gcd(a, b-a);

}

Версия 2 (Использование оператора по модулю)

// Функция для возврата gcd из a и b

int gcd(int a, int b)

{

    if (a == 0) 

       return b;

      

    return gcd(b%a, a);

}

Какой из этих двух вариантов более эффективен?
Версия 1 может занять линейное время, чтобы найти GCD, рассмотрим ситуацию, когда одно из данных чисел намного больше другого. Версия 2, очевидно, более эффективна, так как есть меньше рекурсивных вызовов и требует логарифмического времени.

Рассмотрим ситуацию, когда оператор по модулю не разрешен, можем ли мы оптимизировать версию 1 для более быстрой работы?

Ниже приведены некоторые важные наблюдения. Идея состоит в том, чтобы использовать побитовые операторы. Мы можем найти х / 2, используя х >> 1. Мы можем проверить, является ли x нечетным или четным, используя x & 1.

gcd (a, b) = 2 * gcd (a / 2, b / 2), если и a, и b четные.
gcd (a, b) = gcd (a / 2, b), если a четное и b нечетное.
gcd (a, b) = gcd (a, b / 2), если a нечетно, а b четно.

Ниже приведена реализация C ++.

// Эффективная программа на C ++, когда% и / не разрешены

int gcd(int a, int b)

{

    // Базовые случаи

    if (b == 0 || a == b) return a;

    if (a == 0) return b;

  

    // Если оба a и b четные, разделите оба a

    // и b на 2. И умножаем результат на 2

    if ( (a & 1) == 0 && (b & 1) == 0 )

       return gcd(a>>1, b>>1) << 1;

  

    // Если a четное, а b нечетное, делим a на 2

    if ( (a & 1) == 0 && (b & 1) != 0 )

       return gcd(a>>1, b);

  

    // Если a нечетно, а b четно, делим b на 2

    if ( (a & 1) != 0 && (b & 1) == 0 )

       return gcd(a, b>>1);

  

    // Если оба нечетные, то применяем нормальное вычитание

    // алгоритм. Обратите внимание, что нечетно-нечетный случай всегда

    // преобразует нечетный случай после одной рекурсии

    return (a > b)? gcd(a-b, b): gcd(a, b-a);

}

Эта статья составлена Шивам Агравал. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Алгоритм Евклида, когда% и / операции являются дорогостоящими

0.00 (0%) 0 votes