1. Algorithm Description

Binary GCD also known as Stein’s Algorithm is an algorithm that computes the greatest common divisor of two (positive) numbers . Discovered in 1967 by the Israeli programmer Josef Stein, it’s an alternative to the classical Euclid’s Algorithm, and is considered to be more efficient than this as it’s replacing divisions and multiplications with bitwise operations . The algorithm is recursive by nature, but loops can be used instead of recursion .

The algorithm can be described by the following rules (here and here) . Note that by B_GCD we will refer to a function that returns the greatest common divisor of two positive numbers .

1. B_GCD(0, 0) is not defined, but for convenience we will consider it 0 (zero), so B_GCD(0,0) = 0 ;
2. B_GCD(num1, 0) = num1 and B_GCD(0, num2) = num2 . The reason for this is beacuse zero is divided by everything ;
3. If num1 and num2 are even, B_GCD(num1, num2) = 2 * B_GCD(num1/2, num2/2), as 2 is a common divisor .
4. If num1 is even and num2 is odd, B_GCD(num1, num2) = B_GCD(num1 /2, num2), as 2 is not a common divisor . The steps are the same if num1 is odd and num2 is even : B_GCD(num1, num2) = B_GCD(num1, num2/2) .
5. If both num1 and num2 are odd, then if num1 >= num2 the B_GCD(num1, num2) = B_GCD((num1-num2)/2, num2), else B_GCD(num1, num2) = B_GCD((num2-num1)/2, num1) .
6. Step 4 and 5 are repeated until num1 = num2, or num1 = 0 .

We can also use pseudo code to describe the above algorithm .

Recursive Version of Binary GCD (Stein Algorithm)

The loop-version of the Binary GCD Algorithm

2. Algorithm Implementation (C)

Recursive Version of Binary GCD (Stein Algorithm)

The loop-version of the Binary GCD Algorithm:

If both cases the ouput is 48, and if you look closely, in both cases we’ve used bitwise operations instead of the standard multiplication / division operators .

Note:

If you are interested for the classical Euclid’s Algorithm (for finding the greatest common divisor) + pseudocode and implementation please read this article: Euclid’s Algorithm .

One thought on “Binary GCD (Stein’s Algorithm) in C

  1. Good representation of algorithm in C.
    But I could see some issue.

    /* At this point we know for sure that
    num1 and num2 are odd */
    if (num1 >= num2) {
    num1 = (num1 – num2) >> 1;
    }

    Before this we may have to check if num1 and num2 are equal and then return num1<<pof2.

    Because in case of an example 2 and 4, num1 and num2 will be 1 at this place and it will be an infinite loop.

    So, the code should be

    /* At this point we know for sure that
    num1 and num2 are odd */

    if (num1 == num2) return num1< num2) {
    num1 = (num1 – num2) >> 1;
    }

    Reply

Leave a reply

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url=""> 

required

Are we human, or are we dancer *