Tutorialspoint.dev

Stein’s Algorithm for finding GCD

Stein’s algorithm or binary GCD algorithm is an algorithm that computes the greatest common divisor of two non-negative integers. Stein’s algorithm replaces division with arithmetic shifts, comparisons, and subtraction.

Examples:

Input: a = 17, b = 34 
Output : 17

Input: a = 50, b = 49
Output: 1

Algorithm to find GCD using Stein’s algorithm gcd(a, b)

  1. If both a and b are 0, gcd is zero gcd(0, 0) = 0.
  2. gcd(a, 0) = a and gcd(0, b) = b because everything divides 0.
  3. If a and b are both even, gcd(a, b) = 2*gcd(a/2, b/2) because 2 is a common divisor. Multiplication with 2 can be done with bitwise shift operator.
  4. If a is even and b is odd, gcd(a, b) = gcd(a/2, b). Similarly, if a is odd and b is even, then
    gcd(a, b) = gcd(a, b/2). It is because 2 is not a common divisor.
  5. If both a and b are odd, then gcd(a, b) = gcd(|a-b|/2, b). Note that difference of two odd numbers is even
  6. Repeat steps 3–5 until a = b, or until a = 0. In either case, the GCD is power(2, k) * b, where power(2, k) is 2 raise to the power of k and k is the number of common factors of 2 found in step 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

Python3

# 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
?>


Output :



Gcd of given numbers is 17

Recursive Implementation

CPP

// Recursive 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)
{
    if (a == b)
        return a;
  
    // GCD(0, b) == b; GCD(a, 0) == a,
    // GCD(0, 0) == 0
    if (a == 0)
        return b;
    if (b == 0)
        return a;
  
    // look for factors of 2
    if (~a & 1) // a is even
    {
        if (b & 1) // b is odd
            return gcd(a >> 1, b);
        else // both a and b are even
            return gcd(a >> 1, b >> 1) << 1;
    }
  
    if (~b & 1) // a is odd, b is even
        return gcd(a, b >> 1);
  
    // reduce larger number
    if (a > b)
        return gcd((a - b) >> 1, b);
  
    return gcd((b - a) >> 1, a);
}
  
// Driver code
int main()
{
    int a = 34, b = 17;
    printf("Gcd of given numbers is %d "
                               gcd(a, b));
    return 0;
}

Java

// Recursive 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)
    {
        if (a == b)
            return a;
  
        // GCD(0, b) == b; GCD(a, 0) == a, 
        // GCD(0, 0) == 0
        if (a == 0)
            return b;
        if (b == 0)
            return a;
  
        // look for factors of 2
        if ((~a & 1) == 1) // a is even
        {
            if ((b & 1) == 1) // b is odd
                return gcd(a >> 1, b);
  
            else // both a and b are even
                return gcd(a >> 1, b >> 1) << 1;
        }
  
        // a is odd, b is even
        if ((~b & 1) == 1)
            return gcd(a, b >> 1);
  
        // reduce larger number
        if (a > b)
            return gcd((a - b) >> 1, b);
  
        return gcd((b - a) >> 1, a);
    }
  
    // 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

Python3

# Recursive Python 3 program to 
# implement Stein's Algorithm
  
# Function to implement 
# Stein's Algorithm
def gcd(a, b) :
      
    if (a == b) :
        return a
  
    # GCD(0, b) == b; GCD(a, 0) == a, 
    # GCD(0, 0) == 0 
    if (a == 0) :
        return b
  
    if (b == 0) :
        return a
  
    # look for factors of 2
    # a is even
    if ((~a & 1)== 1 ) :     
          
        # b is odd
        if ((b & 1)== 1) :     
            return gcd(a >> 1, b)
        else :
            # both a and b are even
            return (gcd(a >> 1, b >> 1) << 1)
      
    # a is odd, b is even
    if ((~b & 1)== 1) : 
        return gcd(a, b >> 1)
  
    # reduce larger number
    if (a > b) :
        return gcd((a - b) >> 1, b)
  
    return gcd((b - a) >> 1, a)
  
# Driver code
a, b = 34, 17
print("Gcd of given numbers is "
                       gcd(a, b))
  
# This code is contributed 
# by Nikita Tiwari.

C#

// Recursive C# program to 
// implement Stein's Algorithm
using System;
  
class GFG 
{
  
    // Function to implement
    // Stein's Algorithm
    static int gcd(int a, int b)
    {
        if (a == b)
            return a;
  
        // GCD(0, b) == b;
        // GCD(a, 0) == a,
        // GCD(0, 0) == 0
        if (a == 0)
            return b;
        if (b == 0)
            return a;
  
        // look for factors of 2
        // a is even
        if ((~a & 1) == 1) 
        {
  
            // b is odd
            if ((b & 1) == 1)
                return gcd(a >> 1, b);
  
            else
  
                // both a and b are even
                return gcd(a >> 1, b >> 1) << 1;
        }
  
        // a is odd, b is even
        if ((~b & 1) == 1)
            return gcd(a, b >> 1);
  
        // reduce larger number
        if (a > b)
            return gcd((a - b) >> 1, b);
  
        return gcd((b - a) >> 1, a);
    }
  
    // 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
// Recursive PHP program to
// implement Stein's Algorithm
  
// Function to implement
// Stein's Algorithm
function gcd($a, $b)
{
    if ($a == $b)
        return $a;
  
    /* GCD(0, b) == b; GCD(a, 0) == a,
       GCD(0, 0) == 0 */
    if ($a == 0)
        return $b;
    if ($b == 0)
        return $a;
  
    // look for factors of 2
    if (~$a & 1) // a is even
    {
        if ($b & 1) // b is odd
            return gcd($a >> 1, $b);
        else // both a and b are even
            return gcd($a >> 1, $b >> 1) << 1;
    }
  
    if (~$b & 1) // a is odd, b is even
        return gcd($a, $b >> 1);
  
    // reduce larger number
    if ($a > $b)
        return gcd(($a - $b) >> 1, $b);
  
    return gcd(($b - $a) >> 1, $a);
}
  
// Driver code
$a = 34; $b = 17;
echo "Gcd of given numbers is: "
                     gcd($a, $b);
  
// This code is contributed by aj_36
?>


Output :

Gcd of given numbers is 17

Time Complexity: O(N*N) where N is the number of bits in the larger number.

You may also like – Basic and Extended Euclidian Algorithm

References:

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter