スタインのアルゴリズム または バイナリ GCD アルゴリズム は、2 つの非負の整数の最大公約数を計算するアルゴリズムです。 Stein のアルゴリズムは、除算を算術シフト比較と減算に置き換えます。
例:
入力 : a = 17 b = 34
出力 ：17
入力 : a = 50 b = 49
出力 ：1Javaの部分文字列
Stein のアルゴリズム gcd(a b) を使用して GCD を求めるアルゴリズム
完全な形
アルゴリズムは主に標準を最適化したものです GCD のユークリッド アルゴリズム
- a と b が両方とも 0 の場合、gcd は 0 になります。 gcd(0 0) = 0。
- すべてが 0 を割るので、gcd(a 0) = a および gcd(0 b) = b となります。
- a と b が両方とも偶数の場合、2 は公約数であるため、gcd(a b) = 2*gcd(a/2 b/2) となります。 2 との乗算はビット単位のシフト演算子を使用して実行できます。
- a が偶数で b が奇数の場合、gcd(a b) = gcd(a/2 b) となります。同様に、a が奇数で b が偶数の場合、
gcd(a b) = gcd(a b/2)。 2は公約数ではないからです。 - a と b が両方とも奇数の場合、gcd(a b) = gcd(|a-b|/2 b) となります。 2 つの奇数の差は偶数であることに注意してください
- a = b または a = 0 になるまで手順 3 ～ 5 を繰り返します。いずれの場合も、GCD は power(2 k) * b です。ここで、power(2 k) は 2 の k 乗であり、k は手順 3 で見つかった 2 の公約数です。
// Iterative C++ program to // implement Stein's Algorithm #include
// 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
# 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.
// 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
<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>
// 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 ?> 出力
Gcd of given numbers is 17
時間計算量: O(N*N)
補助スペース: ○(1)
【想定されるアプローチ2】再帰的実装 - O(N*N) 時間と O(N*N) 空間
C++// Recursive C++ program to // implement Stein's Algorithm #include
// 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
# 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.
// 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.
<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>
// 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 ?> 出力
Gcd of given numbers is 17
時間計算量 : O(N*N) ここで、N は大きい方のビット数です。
補助スペース: O(N*N) ここで、N は大きい方のビット数です。
あなたも気に入るかもしれません - 基本および拡張ユークリッド アルゴリズム
Java配列リスト
Euclid の GCD アルゴリズムに対する利点
- Stein のアルゴリズムは、Euclid の GCD アルゴリズムの最適化バージョンです。
- ビット単位のシフト演算子を使用すると、より効率的になります。