/****************************************************************************/
/* Calculo del mcd de dos enteros sin divisiones, solo restas y             */
/* desplazamientos.                                                         */
/*                                                                          */
/* Jaime Suarez <mcripto@bigfoot.com> 2003                                  */
/* en http://elparaiso.mat.uned.es                                            */
/****************************************************************************/

#define PAR(X) !(X&1)

#include <stdio.h>

long mcd(long,long);

main(int argc, char *argv[])
{
	long a,b;

	if (argc!=3) {
		printf("%s <a> <b> calcula el mcd de a y b.\n",argv[0]);
		return 1;
	}
	a=atol(argv[1]); b=atol(argv[2]);
	printf("El m.c.d. de %ld y %ld es %ld\n",a,b,mcd(a,b));
	return 0;
}

long mcd(long a, long b)
{
	if (a==b) return a;
	else if (a<b) return mcd(b,a);
	else if ( PAR(a) &&  PAR(b))  return 2*mcd(a>>1,b>>1);
	else if ( PAR(a) && !PAR(b))  return mcd(a>>1,b);
	else if (!PAR(a) &&  PAR(b))  return mcd(a,b>>1);
	else                          return mcd(a-b,b);
}