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
< ? php function gcd ( $ a , $ b ) { if ( $ a == 0 ) return $ b ; if ( $ b == 0 ) return $ a ; $ 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 ; } $ a = 34 ; $ b = 17 ; echo " Gcd ▁ of ▁ given ▁ numbers ▁ is ▁ " . gcd ( $ a , $ b ) ; ? >