GCD'yi bulmak için Stein Algoritması
GfG Practice'de deneyin 
Çıkış
Çıkış
Stein'ın algoritması veya ikili GCD algoritması Negatif olmayan iki tam sayının en büyük ortak bölenini hesaplayan bir algoritmadır. Stein'ın algoritması, bölme işleminin yerine aritmetik kaydırmalı karşılaştırmalar ve çıkarma işlemlerini getiriyor.
Örnekler:
Giriş : bir = 17 b = 34
Çıkış : 17
Giriş : bir = 50 b = 49
Çıkış : 1
Stein'ın algoritması gcd(a b)'yi kullanarak GCD'yi bulma algoritması
Algoritma temel olarak standartların üzerinde bir optimizasyondur GCD için Öklid Algoritması
- Hem a hem de b 0 ise gcd sıfır gcd(0 0) = 0'dır.
- gcd(a 0) = a ve gcd(0 b) = b çünkü her şey 0'ı bölüyor.
- Eğer a ve b'nin her ikisi de çift ise gcd(a b) = 2*gcd(a/2 b/2) çünkü 2 ortak bölendir. 2 ile çarpma bitsel kaydırma operatörü ile yapılabilir.
- a çift ve b tek ise gcd(a b) = gcd(a/2 b). Benzer şekilde a tek ve b çift ise o zaman
gcd(a b) = gcd(a b/2). Çünkü 2 ortak bölen değildir. - Hem a hem de b tek ise gcd(a b) = gcd(|a-b|/2 b). İki tek sayının farkının çift olduğuna dikkat edin
- a = b veya a = 0'a kadar 3-5 arasındaki adımları tekrarlayın. Her iki durumda da OBEB'in kuvveti (2 k) * b'dir; burada kuvvet (2 k), k'nin kuvvetine 2 yükselir ve k, 3. adımda bulunan 2'nin ortak çarpanlarının sayısıdır.
// Iterative C++ program to // implement Stein's Algorithm #include using namespace std ; // Function to implement // Stein's Algorithm int gcd ( int a int b ) { /* GCD(0 b) == b; GCD(a 0) == a GCD(0 0) == 0 */ if ( a == 0 ) return b ; if ( b == 0 ) return a ; /*Finding K where K is the greatest power of 2 that divides both a and b. */ int k ; for ( k = 0 ; (( a | b ) & 1 ) == 0 ; ++ k ) { a >>= 1 ; b >>= 1 ; } /* Dividing a by 2 until a becomes odd */ while (( a & 1 ) == 0 ) a >>= 1 ; /* From here on 'a' is always odd. */ do { /* If b is even remove all factor of 2 in b */ while (( b & 1 ) == 0 ) b >>= 1 ; /* Now a and b are both odd. Swap if necessary so a <= b then set b = b - a (which is even).*/ if ( a > b ) swap ( a b ); // Swap u and v. b = ( b - a ); } while ( b != 0 ); /* restore common factors of 2 */ return a < < k ; } // Driver code int main () { int a = 34 b = 17 ; printf ( 'Gcd of given numbers is %d n ' gcd ( a b )); return 0 ; }
Java // Iterative Java program to // implement Stein's Algorithm import java.io.* ; class GFG { // Function to implement Stein's // Algorithm static int gcd ( int a int b ) { // GCD(0 b) == b; GCD(a 0) == a // GCD(0 0) == 0 if ( a == 0 ) return b ; if ( b == 0 ) return a ; // Finding K where K is the greatest // power of 2 that divides both a and b int k ; for ( k = 0 ; (( a | b ) & 1 ) == 0 ; ++ k ) { a >>= 1 ; b >>= 1 ; } // Dividing a by 2 until a becomes odd while (( a & 1 ) == 0 ) a >>= 1 ; // From here on 'a' is always odd. do { // If b is even remove // all factor of 2 in b while (( b & 1 ) == 0 ) b >>= 1 ; // Now a and b are both odd. Swap // if necessary so a <= b then set // b = b - a (which is even) if ( a > b ) { // Swap u and v. int temp = a ; a = b ; b = temp ; } b = ( b - a ); } while ( b != 0 ); // restore common factors of 2 return a < < k ; } // Driver code public static void main ( String args [] ) { int a = 34 b = 17 ; System . out . println ( 'Gcd of given ' + 'numbers is ' + gcd ( a b )); } } // This code is contributed by Nikita Tiwari
Python # Iterative Python 3 program to # implement Stein's Algorithm # Function to implement # Stein's Algorithm def gcd ( a b ): # GCD(0 b) == b; GCD(a 0) == a # GCD(0 0) == 0 if ( a == 0 ): return b if ( b == 0 ): return a # Finding K where K is the # greatest power of 2 that # divides both a and b. k = 0 while ((( a | b ) & 1 ) == 0 ): a = a >> 1 b = b >> 1 k = k + 1 # Dividing a by 2 until a becomes odd while (( a & 1 ) == 0 ): a = a >> 1 # From here on 'a' is always odd. while ( b != 0 ): # If b is even remove all # factor of 2 in b while (( b & 1 ) == 0 ): b = b >> 1 # Now a and b are both odd. Swap if # necessary so a <= b then set # b = b - a (which is even). if ( a > b ): # Swap u and v. temp = a a = b b = temp b = ( b - a ) # restore common factors of 2 return ( a < < k ) # Driver code a = 34 b = 17 print ( 'Gcd of given numbers is ' gcd ( a b )) # This code is contributed by Nikita Tiwari.
C# // Iterative C# program to implement // Stein's Algorithm using System ; class GFG { // Function to implement Stein's // Algorithm static int gcd ( int a int b ) { // GCD(0 b) == b; GCD(a 0) == a // GCD(0 0) == 0 if ( a == 0 ) return b ; if ( b == 0 ) return a ; // Finding K where K is the greatest // power of 2 that divides both a and b int k ; for ( k = 0 ; (( a | b ) & 1 ) == 0 ; ++ k ) { a >>= 1 ; b >>= 1 ; } // Dividing a by 2 until a becomes odd while (( a & 1 ) == 0 ) a >>= 1 ; // From here on 'a' is always odd do { // If b is even remove // all factor of 2 in b while (( b & 1 ) == 0 ) b >>= 1 ; /* Now a and b are both odd. Swap if necessary so a <= b then set b = b - a (which is even).*/ if ( a > b ) { // Swap u and v. int temp = a ; a = b ; b = temp ; } b = ( b - a ); } while ( b != 0 ); /* restore common factors of 2 */ return a < < k ; } // Driver code public static void Main () { int a = 34 b = 17 ; Console . Write ( 'Gcd of given ' + 'numbers is ' + gcd ( a b )); } } // This code is contributed by nitin mittal
JavaScript < script > // Iterative JavaScript program to // implement Stein's Algorithm // Function to implement // Stein's Algorithm function gcd ( a b ) { /* GCD(0 b) == b; GCD(a 0) == a GCD(0 0) == 0 */ if ( a == 0 ) return b ; if ( b == 0 ) return a ; /*Finding K where K is the greatest power of 2 that divides both a and b. */ let k ; for ( k = 0 ; (( a | b ) & 1 ) == 0 ; ++ k ) { a >>= 1 ; b >>= 1 ; } /* Dividing a by 2 until a becomes odd */ while (( a & 1 ) == 0 ) a >>= 1 ; /* From here on 'a' is always odd. */ do { /* If b is even remove all factor of 2 in b */ while (( b & 1 ) == 0 ) b >>= 1 ; /* Now a and b are both odd. Swap if necessary so a <= b then set b = b - a (which is even).*/ if ( a > b ){ let t = a ; a = b ; b = t ; } b = ( b - a ); } while ( b != 0 ); /* restore common factors of 2 */ return a < < k ; } // Driver code let a = 34 b = 17 ; document . write ( 'Gcd of given numbers is ' + gcd ( a b )); // This code contributed by gauravrajput1 < /script>
PHP // Iterative php program to // implement Stein's Algorithm // Function to implement // Stein's Algorithm function gcd ( $a $b ) { // GCD(0 b) == b; GCD(a 0) == a // GCD(0 0) == 0 if ( $a == 0 ) return $b ; if ( $b == 0 ) return $a ; // Finding K where K is the greatest // power of 2 that divides both a and b. $k ; for ( $k = 0 ; (( $a | $b ) & 1 ) == 0 ; ++ $k ) { $a >>= 1 ; $b >>= 1 ; } // Dividing a by 2 until a becomes odd while (( $a & 1 ) == 0 ) $a >>= 1 ; // From here on 'a' is always odd. do { // If b is even remove // all factor of 2 in b while (( $b & 1 ) == 0 ) $b >>= 1 ; // Now a and b are both odd. Swap // if necessary so a <= b then set // b = b - a (which is even) if ( $a > $b ) swap ( $a $b ); // Swap u and v. $b = ( $b - $a ); } while ( $b != 0 ); // restore common factors of 2 return $a < < $k ; } // Driver code $a = 34 ; $b = 17 ; echo 'Gcd of given numbers is ' . gcd ( $a $b ); // This code is contributed by ajit ?>
Çıkış
Gcd of given numbers is 17
Zaman Karmaşıklığı: Ç(H*H)
Yardımcı Alan: Ç(1)
[Beklenen Yaklaşım 2] Özyinelemeli Uygulama - Ç(H*H) Zaman ve Ç(H*H) Uzay
C++ // Recursive C++ program to // implement Stein's Algorithm #include using namespace std ; // Function to implement // Stein's Algorithm int gcd ( int a int b ) { if ( a == b ) return a ; // GCD(0 b) == b; GCD(a 0) == a // GCD(0 0) == 0 if ( a == 0 ) return b ; if ( b == 0 ) return a ; // look for factors of 2 if ( ~ a & 1 ) // a is even { if ( b & 1 ) // b is odd return gcd ( a >> 1 b ); else // both a and b are even return gcd ( a >> 1 b >> 1 ) < < 1 ; } if ( ~ b & 1 ) // a is odd b is even return gcd ( a b >> 1 ); // reduce larger number if ( a > b ) return gcd (( a - b ) >> 1 b ); return gcd (( b - a ) >> 1 a ); } // Driver code int main () { int a = 34 b = 17 ; printf ( 'Gcd of given numbers is %d n ' gcd ( a b )); return 0 ; }
Java // Recursive Java program to // implement Stein's Algorithm import java.io.* ; class GFG { // Function to implement // Stein's Algorithm static int gcd ( int a int b ) { if ( a == b ) return a ; // GCD(0 b) == b; GCD(a 0) == a // GCD(0 0) == 0 if ( a == 0 ) return b ; if ( b == 0 ) return a ; // look for factors of 2 if (( ~ a & 1 ) == 1 ) // a is even { if (( b & 1 ) == 1 ) // b is odd return gcd ( a >> 1 b ); else // both a and b are even return gcd ( a >> 1 b >> 1 ) < < 1 ; } // a is odd b is even if (( ~ b & 1 ) == 1 ) return gcd ( a b >> 1 ); // reduce larger number if ( a > b ) return gcd (( a - b ) >> 1 b ); return gcd (( b - a ) >> 1 a ); } // Driver code public static void main ( String args [] ) { int a = 34 b = 17 ; System . out . println ( 'Gcd of given' + 'numbers is ' + gcd ( a b )); } } // This code is contributed by Nikita Tiwari
Python # Recursive Python 3 program to # implement Stein's Algorithm # Function to implement # Stein's Algorithm def gcd ( a b ): if ( a == b ): return a # GCD(0 b) == b; GCD(a 0) == a # GCD(0 0) == 0 if ( a == 0 ): return b if ( b == 0 ): return a # look for factors of 2 # a is even if (( ~ a & 1 ) == 1 ): # b is odd if (( b & 1 ) == 1 ): return gcd ( a >> 1 b ) else : # both a and b are even return ( gcd ( a >> 1 b >> 1 ) < < 1 ) # a is odd b is even if (( ~ b & 1 ) == 1 ): return gcd ( a b >> 1 ) # reduce larger number if ( a > b ): return gcd (( a - b ) >> 1 b ) return gcd (( b - a ) >> 1 a ) # Driver code a b = 34 17 print ( 'Gcd of given numbers is ' gcd ( a b )) # This code is contributed # by Nikita Tiwari.
C# // Recursive C# program to // implement Stein's Algorithm using System ; class GFG { // Function to implement // Stein's Algorithm static int gcd ( int a int b ) { if ( a == b ) return a ; // GCD(0 b) == b; // GCD(a 0) == a // GCD(0 0) == 0 if ( a == 0 ) return b ; if ( b == 0 ) return a ; // look for factors of 2 // a is even if (( ~ a & 1 ) == 1 ) { // b is odd if (( b & 1 ) == 1 ) return gcd ( a >> 1 b ); else // both a and b are even return gcd ( a >> 1 b >> 1 ) < < 1 ; } // a is odd b is even if (( ~ b & 1 ) == 1 ) return gcd ( a b >> 1 ); // reduce larger number if ( a > b ) return gcd (( a - b ) >> 1 b ); return gcd (( b - a ) >> 1 a ); } // Driver code public static void Main () { int a = 34 b = 17 ; Console . Write ( 'Gcd of given' + 'numbers is ' + gcd ( a b )); } } // This code is contributed by nitin mittal.
JavaScript < script > // JavaScript program to // implement Stein's Algorithm // Function to implement // Stein's Algorithm function gcd ( a b ) { if ( a == b ) return a ; // GCD(0 b) == b; GCD(a 0) == a // GCD(0 0) == 0 if ( a == 0 ) return b ; if ( b == 0 ) return a ; // look for factors of 2 if (( ~ a & 1 ) == 1 ) // a is even { if (( b & 1 ) == 1 ) // b is odd return gcd ( a >> 1 b ); else // both a and b are even return gcd ( a >> 1 b >> 1 ) < < 1 ; } // a is odd b is even if (( ~ b & 1 ) == 1 ) return gcd ( a b >> 1 ); // reduce larger number if ( a > b ) return gcd (( a - b ) >> 1 b ); return gcd (( b - a ) >> 1 a ); } // Driver Code let a = 34 b = 17 ; document . write ( 'Gcd of given ' + 'numbers is ' + gcd ( a b )); < /script>
PHP // Recursive PHP program to // implement Stein's Algorithm // Function to implement // Stein's Algorithm function gcd ( $a $b ) { if ( $a == $b ) return $a ; /* GCD(0 b) == b; GCD(a 0) == a GCD(0 0) == 0 */ if ( $a == 0 ) return $b ; if ( $b == 0 ) return $a ; // look for factors of 2 if ( ~ $a & 1 ) // a is even { if ( $b & 1 ) // b is odd return gcd ( $a >> 1 $b ); else // both a and b are even return gcd ( $a >> 1 $b >> 1 ) < < 1 ; } if ( ~ $b & 1 ) // a is odd b is even return gcd ( $a $b >> 1 ); // reduce larger number if ( $a > $b ) return gcd (( $a - $b ) >> 1 $b ); return gcd (( $b - $a ) >> 1 $a ); } // Driver code $a = 34 ; $b = 17 ; echo 'Gcd of given numbers is: ' gcd ( $a $b ); // This code is contributed by aj_36 ?>
Çıkış
Gcd of given numbers is 17
Zaman Karmaşıklığı : O(N*N) burada N, büyük sayıdaki bit sayısıdır.
Yardımcı Alan: O(N*N) burada N, büyük sayıdaki bit sayısıdır.
Şunları da beğenebilirsiniz - Temel ve Genişletilmiş Öklid Algoritması
Öklid'in GCD Algoritmasına Göre Avantajları
- Stein'ın algoritması Euclid'in GCD Algoritmasının optimize edilmiş versiyonudur.
- bitsel kaydırma operatörünün kullanılması daha verimlidir.
