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