Stein 's Algorithm for finding GCD | Function to implement Stein 's Algorithm ; GCD ( 0 , b ) == b ; GCD ( a , 0 ) == a , GCD ( 0 , 0 ) == 0 ; look for factors of 2 a is even ; b is odd ; both a and b are even ; a is odd , b is even ; reduce larger number ; Driver code
def gcd ( a , b ) : NEW_LINE INDENT if ( a == b ) : NEW_LINE INDENT return a NEW_LINE DEDENT if ( a == 0 ) : NEW_LINE INDENT return b NEW_LINE DEDENT if ( b == 0 ) : NEW_LINE INDENT return a NEW_LINE DEDENT if ( ( ~ a & 1 ) == 1 ) : NEW_LINE INDENT if ( ( b & 1 ) == 1 ) : NEW_LINE INDENT return gcd ( a >> 1 , b ) NEW_LINE DEDENT else : NEW_LINE INDENT return ( gcd ( a >> 1 , b >> 1 ) << 1 ) NEW_LINE DEDENT DEDENT if ( ( ~ b & 1 ) == 1 ) : NEW_LINE INDENT return gcd ( a , b >> 1 ) NEW_LINE DEDENT if ( a > b ) : NEW_LINE INDENT return gcd ( ( a - b ) >> 1 , b ) NEW_LINE DEDENT return gcd ( ( b - a ) >> 1 , a ) NEW_LINE DEDENT a , b = 34 , 17 NEW_LINE print ( " Gcd ▁ of ▁ given ▁ numbers ▁ is ▁ " , gcd ( a , b ) ) NEW_LINE