Eclipse Wiki Weblog

Thursday September 11, 2008

Extended Euclidean algorithm in Java

Jeremy Watts joined the MathEclipse developer team and provided the following implementation for the Extended Euclidean algorithm in Java.

The example program calculates the ExtendedGCD[12,60,256,282] and prints the result [2, [1470, 0, -70, 1]] to the console. This means that the greatest common divisor 2 could be calculated as 1470*12 + 0*60 + (-70)*256 + 1*282.

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class ExtendedGCD {

	public ExtendedGCD() {
	}

	public static void main(String[] args) {
		// calculate ExtendedGCD(12,60,256,282)
		List<BigInteger> argumentsList = new ArrayList<BigInteger>();
		argumentsList.add(BigInteger.valueOf(12));
		argumentsList.add(BigInteger.valueOf(60));
		argumentsList.add(BigInteger.valueOf(256));
		argumentsList.add(BigInteger.valueOf(282));
		try {
			Object[] results;
			BigInteger gcd = argumentsList.get(0);
			BigInteger factor = BigInteger.ONE;
			BigInteger[] subBezouts = new BigInteger[argumentsList.size()];
			results = extendedGCD(argumentsList.get(1), gcd);
			gcd = (BigInteger) results[0];
			subBezouts[0] = ((BigInteger[]) results[1])[0];
			subBezouts[1] = ((BigInteger[]) results[1])[1];
			for (int i = 2; i < argumentsList.size(); i++) {
				results = extendedGCD(argumentsList.get(i), gcd);
				gcd = (BigInteger) results[0];
				factor = ((BigInteger[]) results[1])[0];
				for (int j = 0; j < i; j++) {
					subBezouts[j] = subBezouts[j].multiply(factor);
				}
				subBezouts[i] = ((BigInteger[]) results[1])[1];
			}
			List list = new ArrayList();
			list.add(gcd);

			List<BigInteger> subList = new ArrayList<BigInteger>();
			for (int i = 0; i < subBezouts.length; i++) {
				subList.add(subBezouts[i]);
			}
			list.add(subList);
			// prints: [2, [1470, 0, -70, 1]]
			System.out.println(list);
		} catch (ArithmeticException ae) {
			ae.printStackTrace();
		}
	}

	/**
	 * Returns the gcd of two positive numbers plus the Bezout relation
	 */
	public static Object[] extendedGCD(BigInteger numberOne, BigInteger numberTwo) {
		Object[] results = new Object[2];
		BigInteger[] divisionResult = new BigInteger[2];
		BigInteger dividend;
		BigInteger divisor;
		BigInteger quotient;
		BigInteger remainder;
		BigInteger xValue;
		BigInteger yValue;
		BigInteger tempValue;
		BigInteger lastxValue;
		BigInteger lastyValue;
		BigInteger gcd = BigInteger.ONE;
		BigInteger mValue = BigInteger.ONE;
		BigInteger nValue = BigInteger.ONE;
		boolean exchange;

		remainder = BigInteger.ONE;
		xValue = BigInteger.ZERO;
		lastxValue = BigInteger.ONE;
		yValue = BigInteger.ONE;
		lastyValue = BigInteger.ZERO;
		if ((!((numberOne.compareTo(BigInteger.ZERO) == 0) || (numberTwo.compareTo(BigInteger.ZERO) == 0)))
				&& (((numberOne.compareTo(BigInteger.ZERO) == 1) && (numberTwo.compareTo(BigInteger.ZERO) == 1)))) {
			if (numberOne.compareTo(numberTwo) == 1) {
				exchange = false;
				dividend = numberOne;
				divisor = numberTwo;
			} else {
				exchange = true;
				dividend = numberTwo;
				divisor = numberOne;
			}

			while (remainder.compareTo(BigInteger.ZERO) != 0) {
				divisionResult = dividend.divideAndRemainder(divisor);
				quotient = divisionResult[0];
				remainder = divisionResult[1];

				dividend = divisor;
				divisor = remainder;

				tempValue = xValue;
				xValue = lastxValue.subtract(quotient.multiply(xValue));
				lastxValue = tempValue;

				tempValue = yValue;
				yValue = lastyValue.subtract(quotient.multiply(yValue));
				lastyValue = tempValue;
			}

			gcd = dividend;
			if (exchange == false) {
				mValue = lastxValue;
				nValue = lastyValue;
			} else {
				mValue = lastyValue;
				nValue = lastxValue;
			}
		} else {
			throw new ArithmeticException("ExtendedGCD has wrong arguments");
		}
		results[0] = gcd;
		BigInteger[] values = new BigInteger[2];
		values[0] = nValue;
		values[1] = mValue;
		results[1] = values;
		return results;
	}
}