Алгоритм Штейна для поиска НОД

Опубликовано: 20 Января, 2022

Алгоритм Штейна или двоичный алгоритм НОД - это алгоритм, который вычисляет наибольший общий делитель двух неотрицательных целых чисел. Алгоритм Штейна заменяет деление арифметическими сдвигами, сравнениями и вычитанием.

Примеры:

 Ввод: a = 17, b = 34 
Выход: 17

Ввод: a = 50, b = 49
Выход: 1

Алгоритм поиска НОД с использованием алгоритма Стейна gcd (a, b)

Если и a, и b равны 0, gcd равен нулю gcd (0, 0) = 0.
gcd (a, 0) = a и gcd (0, b) = b, потому что все делит 0.
Если a и b оба четные, gcd (a, b) = 2 * gcd (a / 2, b / 2), потому что 2 является общим делителем. Умножение на 2 можно выполнить с помощью оператора побитового сдвига.
Если a четное, а b нечетное, gcd (a, b) = gcd (a / 2, b). Аналогично, если a нечетное, а b четное, то
gcd (a, b) = gcd (a, b / 2). Это потому, что 2 не является общим делителем.
Если и a, и b нечетные, то gcd (a, b) = gcd (| ab | / 2, b). Обратите внимание, что разница двух нечетных чисел четная.
Повторяйте шаги 3–5 до тех пор, пока a = b или пока a = 0. В любом случае НОД представляет собой степень (2, k) * b, где степень (2, k) равна 2, возведение в степень k, а k равно количество общих делителей 2, найденных на шаге 2.

Iterative Implementation

C++

// Iterative C++ program to
// implement Stein"s Algorithm
#include <bits/stdc++.h>
using namespace std;
 
// Function to implement
// Stein"s Algorithm
int gcd(int a, int b)
{
    /* GCD(0, b) == b; GCD(a, 0) == a,
       GCD(0, 0) == 0 */
    if (a == 0)
        return b;
    if (b == 0)
        return a;
 
    /*Finding K, where K is the
      greatest power of 2
      that divides both a and b. */
    int k;
    for (k = 0; ((a | b) & 1) == 0; ++k)
    {
        a >>= 1;
        b >>= 1;
    }
 
    /* Dividing a by 2 until a becomes odd */
    while ((a & 1) == 0)
        a >>= 1;
 
    /* From here on, "a" is always odd. */
    do
    {
        /* If b is even, remove all factor of 2 in b */
        while ((b & 1) == 0)
            b >>= 1;
 
        /* Now a and b are both odd.
           Swap if necessary so a <= b,
           then set b = b - a (which is even).*/
        if (a > b)
            swap(a, b); // Swap u and v.
 
        b = (b - a);
    }while (b != 0);
 
    /* restore common factors of 2 */
    return a << k;
}
 
// Driver code
int main()
{
    int a = 34, b = 17;
    printf("Gcd of given numbers is %d
", gcd(a, b));
    return 0;
}

Java

// Iterative Java program to
// implement Stein"s Algorithm
import java.io.*;
 
class GFG {
 
    // Function to implement Stein"s
    // Algorithm
    static int gcd(int a, int b)
    {
        // GCD(0, b) == b; GCD(a, 0) == a,
        // GCD(0, 0) == 0
        if (a == 0)
            return b;
        if (b == 0)
            return a;
 
        // Finding K, where K is the greatest
        // power of 2 that divides both a and b
        int k;
        for (k = 0; ((a | b) & 1) == 0; ++k)
        {
            a >>= 1;
            b >>= 1;
        }
 
        // Dividing a by 2 until a becomes odd
        while ((a & 1) == 0)
            a >>= 1;
 
        // From here on, "a" is always odd.
        do
        {
            // If b is even, remove
            // all factor of 2 in b
            while ((b & 1) == 0)
                b >>= 1;
 
            // Now a and b are both odd. Swap
            // if necessary so a <= b, then set
            // b = b - a (which is even)
            if (a > b)
            {
                // Swap u and v.
                int temp = a;
                a = b;
                b = temp;
            }
 
            b = (b - a);
        } while (b != 0);
 
        // restore common factors of 2
        return a << k;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int a = 34, b = 17;
 
        System.out.println("Gcd of given "
                           + "numbers is " + gcd(a, b));
    }
}
 
// This code is contributed by Nikita Tiwari

Python

# Iterative Python 3 program to
# implement Stein"s Algorithm
 
# Function to implement
# Stein"s Algorithm
 
 
def gcd(a, b):
 
    # GCD(0, b) == b; GCD(a, 0) == a,
    # GCD(0, 0) == 0
    if (a == 0):
        return b
 
    if (b == 0):
        return a
 
    # Finding K, where K is the
    # greatest power of 2 that
    # divides both a and b.
    k = 0
 
    while(((a | b) & 1) == 0):
        a = a >> 1
        b = b >> 1
        k = k + 1
 
    # Dividing a by 2 until a becomes odd
    while ((a & 1) == 0):
        a = a >> 1
 
    # From here on, "a" is always odd.
    while(b != 0):
 
        # If b is even, remove all
        # factor of 2 in b
        while ((b & 1) == 0):
            b = b >> 1
 
        # Now a and b are both odd. Swap if
        # necessary so a <= b, then set
        # b = b - a (which is even).
        if (a > b):
 
            # Swap u and v.
            temp = a
            a = b
            b = temp
 
        b = (b - a)
 
    # restore common factors of 2
    return (a << k)
 
 
# Driver code
a = 34
b = 17
 
print("Gcd of given numbers is ", gcd(a, b))
 
# This code is contributed by Nikita Tiwari.

C#

// Iterative C# program to implement
// Stein"s Algorithm
using System;
 
class GFG {
 
    // Function to implement Stein"s
    // Algorithm
    static int gcd(int a, int b)
    {
 
        // GCD(0, b) == b; GCD(a, 0) == a,
        // GCD(0, 0) == 0
        if (a == 0)
            return b;
        if (b == 0)
            return a;
 
        // Finding K, where K is the greatest
        // power of 2 that divides both a and b
        int k;
        for (k = 0; ((a | b) & 1) == 0; ++k)
        {
            a >>= 1;
            b >>= 1;
        }
 
        // Dividing a by 2 until a becomes odd
        while ((a & 1) == 0)
            a >>= 1;
 
        // From here on, "a" is always odd
        do
        {
            // If b is even, remove
            // all factor of 2 in b
            while ((b & 1) == 0)
                b >>= 1;
 
            /* Now a and b are both odd. Swap
            if necessary so a <= b, then set
            b = b - a (which is even).*/
            if (a > b) {
 
                // Swap u and v.
                int temp = a;
                a = b;
                b = temp;
            }
 
            b = (b - a);
        } while (b != 0);
 
        /* restore common factors of 2 */
        return a << k;
    }
 
    // Driver code
    public static void Main()
    {
        int a = 34, b = 17;
 
        Console.Write("Gcd of given "
                      + "numbers is " + gcd(a, b));
    }
}
 
// This code is contributed by nitin mittal

PHP

<?php
// Iterative php program to
// implement Stein"s Algorithm
 
// Function to implement
// Stein"s Algorithm
function gcd($a, $b)
{
    // GCD(0, b) == b; GCD(a, 0) == a,
    // GCD(0, 0) == 0
    if ($a == 0)
        return $b;
    if ($b == 0)
        return $a;
 
    // Finding K, where K is the greatest
    // power of 2 that divides both a and b.
    $k;
    for ($k = 0; (($a | $b) & 1) == 0; ++$k)
    {
        $a >>= 1;
        $b >>= 1;
    }
 
    // Dividing a by 2 until a becomes odd
    while (($a & 1) == 0)
        $a >>= 1;
 
    // From here on, "a" is always odd.
    do
    {
         
        // If b is even, remove
        // all factor of 2 in b
        while (($b & 1) == 0)
            $b >>= 1;
 
        // Now a and b are both odd. Swap
        // if necessary so a <= b, then set
        // b = b - a (which is even)
        if ($a > $b)
            swap($a, $b); // Swap u and v.
 
        $b = ($b - $a);
    } while ($b != 0);
 
    // restore common factors of 2
    return $a << $k;
}
 
// Driver code
$a = 34; $b = 17;
echo "Gcd of given numbers is " .
                     gcd($a, $b);
 
// This code is contributed by ajit
?>

Javascript

<script>
 
// Iterative JavaScript program to
// implement Stein"s Algorithm
 
// Function to implement
// Stein"s Algorithm
function gcd( a,  b)
{
    /* GCD(0, b) == b; GCD(a, 0) == a,
       GCD(0, 0) == 0 */
    if (a == 0)
        return b;
    if (b == 0)
        return a;
 
    /*Finding K, where K is the
      greatest power of 2
      that divides both a and b. */
    let k;
    for (k = 0; ((a | b) & 1) == 0; ++k)
    {
        a >>= 1;
        b >>= 1;
    }
 
    /* Dividing a by 2 until a becomes odd */
    while ((a & 1) == 0)
        a >>= 1;
 
    /* From here on, "a" is always odd. */
    do
    {
        /* If b is even, remove all factor of 2 in b */
        while ((b & 1) == 0)
            b >>= 1;
 
        /* Now a and b are both odd.
           Swap if necessary so a <= b,
           then set b = b - a (which is even).*/
        if (a > b){
        let t = a;
        a = b;
        b = t;
        }
 
        b = (b - a);
    }while (b != 0);
 
    /* restore common factors of 2 */
    return a << k;
}
 
// Driver code
 
    let a = 34, b = 17;
    document.write("Gcd of given numbers is "+ gcd(a, b));
 
// This code contributed by gauravrajput1
 
</script>

Output

Gcd of given numbers is 17

Алгоритм Штейна для поиска НОД

C++

Java

Python

C#

PHP

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ