Lo que tenemos que hacer ahora es arreglar la función
gcd() para que funcione en todos los casos posibles.
La función tiene que ser capaz de lidiar con todo tipo de valores \( m, n \), y retornar un valor correcto, o con sentido.
Una de las propiedades del máximo común divisor es que no depende del signo:
\( gcd(m,n)= gcd(|m|,|n|). \)
Así, cuando alguno de los parámetros \( m,n \), es negativo, esto no tiene que importar.
Lo que haremos será sustituir los parámetros originales \( m, n \), por sus valores absolutos,
mediante la sentencia siguiente:
m = abs(m);
n = abs(n);
Aquí es necesario invocar la función abs(), que retorna el valor absoluto de un número.
Podemos usar las matemáticas predefinidas de C, o bien realizar nuestra propia versión.
Suelo preferir no sobrecargar los programas invocando librerías.
Así que voy a poner mi propia versión de "función valor absoluto".
He aquí el prototipo:
int abs(int);
La función
abs() tomará como parámetro un número entero (tipo
int) y retornará como resultado su valor absoluto, como un dato de tipo
int.
Es conveniente documentar correctamente el programa indicando estas dos propiedades matemáticas:
* La propiedad lógico-matemática que le da sentido a una determinada sentencia del programa.
* La condición lógica que siempre se cumple tras ejecutar dicha sentencia.
Así, mejor escribimos las sentencias anteriores rodeadas de comentarios:
m = abs(m);
n = abs(n);
/* gcd(m, n) == gcd(abs(m), abs(n)) */
/* m >= 0, n >= 0 */
La 3er línea contiene un comentario que expresa que el máximo común divisor será invariante respecto la aplicación de valor absoluto a cada parámetro. Esto es consecuente con la matemática subyacente.
En la 4ta línea se expresan las condiciones \( m\geq 0, n\geq 0 \), que son invariantes del algoritmo.
Lo que significa es que: siempre que el programa llegue a ese punto de ejecución, las condiciones \( m\geq 0, n\geq 0 \), son verdaderas.
Resuelto el problema de los signos, tenemos ahora que intentar poner las cosas en el formato cómodo que ya habíamos estudiado, a saber: \( m>n>0 \).
Hay que manejar los casos en que algún parámetro es 0, o en que ambos parámetros son iguales, etc.
Lo que conviene hacer, digo yo, es reordenar los parámetros de manera que \( m\geq n \).
Y como ya hemos logrado que ambos sean no-negativos, tendremos más precisamente: \( m\geq n\geq 0 \).
Si ya fuera cierto que \( m\geq n \), entonces no haríamos nada.
En cambio, si \( m<n \), intercambiaríamos los papeles de \( m, n \).
Esto se puede hacer sin problemas porque la operación de máximo común divisor es "conmutativa", es decir, no varía si invertimos los parámetros:
\( gcd(m, n) = gcd(n,m). \)
Esta propiedad es la que nos autoriza a intercambiar los valores de las variables para que nos quede del modo que a nosotros nos resulte cómodo.
El intercambio de valores entre \( m, n \), requiere, como es usual, el uso de una variable temporal.
Por ahora vamos a hacerlo de forma sencilla, así:
/* swap m and n ... */
{
int temp = m; m = n; n = m;
}
La sentencia completa luce así:
if (m < n)
/* swap m and n ... */
{
int temp = m; m = n; n = m;
}
/* gcd(m, n) == gcd(n, m) */
/* m >= n >= 0*/
Como se puede apreciar, tras realizar el
"swap" (intercambio),
se cumplirá siempre la condición invariante deseada: \( m \geq n\geq 0 \).
Hemos agregado también una línea de comentario que explica el resultado matemático que se obtendrá como consecuencia del
"swap": la función \( gcd(m, n) \) dará el mismo resultado que \( gcd(n, m) \).
El siguiente caso que quisiéramos descartar de inmediato es cuando \( m = n = 0 \).
Este caso es el único que no da un número entero válido como resultado.
Pero la función
gcd() necesita retornar un número entero, porque está declarada como
int.
¿Cómo lo arreglamos?
Lo primero que recordamos aquí es que, cuando el valor gcd(m, n) está bien definido, es un número entero \( \geq 0 \).
Entonces podemos usar valores negativos a modo de "valores señalizadores" para indicar que algo anduvo mal.
Esto deberá estar documentado en la cabecera de la función
gcd(), pero lo haremos luego.
Ahora simplemente manejamos el caso \( m = n = 0 \) retornando un valor negativo sencillo, como \( -1 \), que para nosotros va a significar:
"señal de valor infinito" o
"señal de resultado no definido".
if ( (m == 0) && (n == 0) )
return -1;
/* m > 0, m >= n >= 0 */
Una vez que ese "if" ha pasado al siguiente punto de ejecución del programa,
obtenemos que \( m\geq n\geq 0 \), como antes, pero además sabemos que \( m>0 \).
Estas dos condiciones las ponemos como comentario en ese punto de ejecución.
Una vez que hemos descartado el caso insalubre de \( m = n = 0 \),
todavía nos gustaría sacarnos de encima los casos triviales en que \( m = n \neq 0 \).
En esta situación es fácil calcular el máximo común divisor:
\( gcd(m, m) = m. \)
Sin embargo, lo que realmente nos importa es sacarnos de encima el caso \( m = n \),
porque nuestro algoritmo original funcionaba de maravillas sólo para \( m > n \),
y queremos poder aprovechar eso.
Supongamos que \( m = n \). Como ya hemos descartado el caso \( m = n = 0 \), entonces tenemos la certeza ahora que \( m = n \neq 0 \), y por lo tanto el valor el máximo común divisor es \( m \), y no \( \infty \).
Aquí vemos, pues, un ejemplo de la utilidad de los invariantes: nos ahorra tener que evaluar condiciones que previamente ya hemos tomado en cuenta.
El código sería éste:
if (m == n)
return m;
/* m == n > 0 ---> gcd(m, n) == m */
/* m > n >= 0 */
En la 3er línea ponemos en un comentario la conclusión lógica de las operaciones que hemos efectuado: "en caso de que \( m = n > 0 \), la función \( gcd(m, n) \) retornará \( m \)".
En la 4ta línea tomamos nota del estado en que se encuentran las variables m, n, en el presente punto de ejecución. Al llegar allí podemos estar seguros de que \( m > n \geq 0 \).
Sin embargo, vemos que todavía no nos hemos sacado de encima el posible caso en que n = 0.
Y puede que tampoco sea necesario...
Pero por ahora lo vamos a descartar sin más, y más tarde mejoraremos el algoritmo.
Si \( n = 0 \), como ahora \( m > n \), obtenemos \( m > 0 \), y entonces \( gcd(m, 0) = m \), con lo cual tranquilamente podemos retornar el valor \( m \).
Habiendo ya descartado todos los casos "molestos", llegamos finalmente a la situación principal deseada, en que \( m > n > 0 \).
Aquí basta insertar lo que ya teníamos antes.
Además voy a agregar la línea de comentario que justifica el algoritmo:
/* gcd(m, n) == gcd(n, m % n) */
La función
gcd() completa quedaría así:
int gcd(int m, int n) {
/* gcd(m, n) devuelve el máximo común divisor de los enteros m y n */
/* gcd(m, n) siempre es >= 0 */
/* Excepción: gcd(0, 0) retorna -1, que significa: "valor infinito/indefinido" */
m = abs(m); n = abs(n);
/* gcd(m, n) == gcd(abs(m), abs(n)) */
/* m >= 0, n >= 0 */
if (m < n)
/* swap m and n ... */
{
int temp = m; m = n; n = m;
}
/* gcd(m, n) == gcd(n, m) */
/* m >= n */
if ((m == 0) && (n == 0))
/* ---> m == n == 0 */
return -1;
/* m > 0, m >= n >= 0 */
if (m == n)
return m;
/* m > 0 ---> gcd(m, m) = m */
/* m > n >= 0 */
if (n == 0)
return m;
/* gcd(m, 0) == m */
/* m > n > 0 */
do {
/* m > n > 0 */
/* gcd(m, n) == gcd(n, m % n) */
int temp = n; n = m % n; m = temp;
/* viejo m > viejo n == nuevo m > nuevo n == (viejo m) % (viejo n) */
} while(n > 0);
/* n == 0, m == gcd(original m, original n) */
return m;
}
En el siguiente post haremos retoques totalmente inútiles,
pero que ilustran algunas técnicas de programación.
