El algoritmo de Stein o algoritmo GCD binario es un algoritmo que calcula el máximo común divisor de dos números enteros no negativos. El algoritmo de Stein reemplaza la división con cambios aritméticos, comparaciones y restas.
Ejemplos:
Input: a = 17, b = 34 Output : 17 Input: a = 50, b = 49 Output: 1
Algoritmo para encontrar GCD usando el algoritmo de Stein gcd(a, b)
- Si tanto a como b son 0, mcd es cero mcd(0, 0) = 0.
- mcd(a, 0) = a y mcd(0, b) = b porque todo divide a 0.
- Si a y b son pares, mcd(a, b) = 2*mcd(a/2, b/2) porque 2 es un divisor común. La multiplicación con 2 se puede hacer con el operador de desplazamiento bit a bit.
- Si a es par y b es impar, mcd(a, b) = mcd(a/2, b). De manera similar, si a es impar y b es par, entonces
mcd(a, b) = mcd(a, b/2). Es porque 2 no es un divisor común. - Si tanto a como b son impares, entonces mcd(a, b) = mcd(|ab|/2, b). Tenga en cuenta que la diferencia de dos números impares es par
- Repita los pasos 3 a 5 hasta que a = b, o hasta que a = 0. En cualquier caso, el MCD es potencia(2, k) * b, donde potencia(2, k) es 2 elevado a la potencia de k y k es el número de factores comunes de 2 encontrados en el paso 3.
Implementación iterativa
C++
// Iterative C++ program to
// implement Stein's Algorithm
#include <bits/stdc++.h>
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
Python3
# 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
PHP
<?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
?>
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>
Producción
Gcd of given numbers is 17
Complejidad temporal: O(N*N)
Espacio auxiliar: O(1)
Implementación recursiva
C++
// Recursive C++ program to
// implement Stein's Algorithm
#include <bits/stdc++.h>
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
Python3
# 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.
PHP
<?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
?>
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>
Producción
Gcd of given numbers is 17
Complejidad de tiempo : O(N*N) donde N es el número de bits en el número mayor.
Espacio auxiliar: O(N*N) donde N es el número de bits del número mayor.
También te puede interesar: algoritmo euclidiano básico y extendido
Ventajas sobre el algoritmo GCD de Euclides
- El algoritmo de Stein es una versión optimizada del algoritmo GCD de Euclid.
- es más eficiente usando el operador de desplazamiento bit a bit.
Este artículo es una contribución de Aarti_Rathi y Rahul Agrawal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA