/*                                                      */
/*      euclidean algorithm                             */
/*      given a, b, returns x, y, m such that           */
/*        a * x  +  b * y  =  m  =  gcd(a, b)           */
/*                                                      */
euclid(ain, bin, x, y, m)
int ain, bin, *x, *y, *m;
{

	int a, b, q, r, sign, signa, signb, ycurrent, ynext, yprevious;

	if (ain >= 0)
	{
		signa = 1;
		a = ain;
	}
	else
	{
		signa = -1;
		a = -ain;
	}

	if (bin >= 0)
	{
		signb = 1;
		b = bin;
	}
	else
	{
		signb = -1;
		b = -bin;
	}

	if(a == 0)
	{
		*x = 0;
		*y = signb;
		*m = b;
	}

	if(b == 0)
	{
		*x = signa;
		*y = 0;
		*m = a;
	}

	yprevious = 0;
	ycurrent = 1;
	q = a / b;
	r = a % b;
	sign = 1;
	while (r != 0)
	{
		sign = -sign;
		ynext = q * ycurrent + yprevious;
		yprevious = ycurrent;
		ycurrent = ynext;
		a = b;
		b = r;
		q = a / b;
		r = a % b;
	}
	*y = (sign == signb) ? ycurrent : -ycurrent;
	*x = ( b - bin * (*y) ) / ain;
	*m = b;
}