Stein 's Algorithm for finding GCD | 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
def gcd ( a , b ) : NEW_LINE INDENT if ( a == 0 ) : NEW_LINE INDENT return b NEW_LINE DEDENT if ( b == 0 ) : NEW_LINE INDENT return a NEW_LINE DEDENT k = 0 NEW_LINE while ( ( ( a b ) & 1 ) == 0 ) : NEW_LINE INDENT a = a >> 1 NEW_LINE b = b >> 1 NEW_LINE k = k + 1 NEW_LINE DEDENT while ( ( a & 1 ) == 0 ) : NEW_LINE INDENT a = a >> 1 NEW_LINE DEDENT while ( b != 0 ) : NEW_LINE INDENT while ( ( b & 1 ) == 0 ) : NEW_LINE INDENT b = b >> 1 NEW_LINE DEDENT if ( a > b ) : NEW_LINE INDENT temp = a NEW_LINE a = b NEW_LINE b = temp NEW_LINE DEDENT b = ( b - a ) NEW_LINE DEDENT return ( a << k ) NEW_LINE DEDENT a = 34 NEW_LINE b = 17 NEW_LINE print ( " Gcd ▁ of ▁ given ▁ numbers ▁ is ▁ " , gcd ( a , b ) ) NEW_LINE