Steinov algoritam za pronalaženje GCD
Isprobajte na GfG Practice 
Izlaz
Izlaz
Steinov algoritam ili binarni GCD algoritam je algoritam koji izračunava najveći zajednički djelitelj dva nenegativna cijela broja. Steinov algoritam zamjenjuje dijeljenje aritmetičkim pomacima, usporedbama i oduzimanjem.
Primjeri:
Ulazni : a = 17 b = 34
Izlaz : 17
Ulazni : a = 50 b = 49
Izlaz : 1
Algoritam za pronalaženje GCD-a koristeći Steinov algoritam gcd(a b)
Algoritam je uglavnom optimizacija u odnosu na standard Euklidski algoritam za GCD
- Ako su i a i b 0 gcd je nula gcd(0 0) = 0.
- gcd(a 0) = a i gcd(0 b) = b jer sve dijeli 0.
- Ako su a i b parni, gcd(a b) = 2*gcd(a/2 b/2) jer je 2 zajednički djelitelj. Množenje s 2 može se izvesti operatorom pomaka u bitovima.
- Ako je a paran, a b neparan gcd(a b) = gcd(a/2 b). Slično ako je a neparan, a b paran tada
gcd(a b) = gcd(a b/2). To je zato što 2 nije zajednički djelitelj. - Ako su i a i b neparni tada je gcd(a b) = gcd(|a-b|/2 b). Imajte na umu da je razlika dvaju neparnih brojeva parna
- Ponavljajte korake 3–5 dok a = b ili dok a = 0. U oba slučaja GCD je potencija (2 k) * b gdje je potencija (2 k) 2 podignuta na potenciju k, a k je broj zajedničkih faktora od 2 pronađenih u koraku 3.
// 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 ?>
Izlaz
Gcd of given numbers is 17
Vremenska složenost: O(N*N)
Pomoćni prostor: O(1)
[Očekivani pristup 2] Rekurzivna implementacija - O(N*N) Vrijeme i O(N*N) Prostor
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 ?>
Izlaz
Gcd of given numbers is 17
Vremenska složenost : O(N*N) gdje je N broj bitova u većem broju.
Pomoćni prostor: O(N*N) gdje je N broj bitova u većem broju.
Možda će vam se također svidjeti - Osnovni i prošireni euklidski algoritam
Prednosti u odnosu na Euklidov GCD algoritam
- Steinov algoritam je optimizirana verzija Euklidovog GCD algoritma.
- učinkovitiji je korištenjem operatora pomaka po bitovima.
