# need help with lehmer's gcd algorithm code

• April 17th, 2013, 03:43 AM
mirjamkolar
need help with lehmer's gcd algorithm code
Hey guys!

I have a problem with programming a Lehmer's gcd algorithm. It works fine but the problem is that it's slower than the basic euclidean algorithm. Can anyone tell me where is the problem.
This is my code in java:

private static BigInteger LEHMER(BigInteger A0, BigInteger A1) {

BigInteger compareNum = new new BigInteger("9223372036854775808"); //math.pow(2,63)

while( A1.compareTo(compareNum) >= 0) {
int h = A0.bitCount()+1 - 64; //or maybe 63
BigInteger a0 = A0.shiftRight(h);
BigInteger a1 = A1.shiftRight(h);

BigInteger u0 = new BigInteger("1");
BigInteger u1 = new BigInteger("0");
BigInteger v0 = new BigInteger("0");
BigInteger v1 = new BigInteger("1");

break;

BigInteger r = a0.subtract(q0.multiply(a1)); a0 = a1; a1 = r;
r = u0.subtract(q0.multiply(u1)); u0 = u1; u1 = r;
r = v0.subtract(q0.multiply(v1)); v0 = v1; v1 = r;
}

if (v0.equals(BigInteger.ZERO)) {
BigInteger R = A0.remainder(A1); A0 = A1; A1 = R;
}
else {
A0 = R; A1 = T;
}
}

while (A1.compareTo(BigInteger.ZERO) > 0) {
BigInteger R = A0.remainder(A1); A0 = A1; A1 = R;
}

return A0;
}

The basic Euclidean algorithm:

private static BigInteger EA(BigInteger a, BigInteger b) {

while ( !b.equals(BigInteger.ZERO) ) {
BigInteger q = a.divide(b);
BigInteger r = a.subtract(q.multiply(b)); a = b; b = r;
}

return a;
}

• April 17th, 2013, 04:05 AM
mirjamkolar
need help with lehmer's gcd algorithm code
Hey guys!

I have a problem with programming a Lehmer's gcd algorithm. It works fine but the problem is that it's slower than the basic euclidean algorithm. Can anyone tell me where is the problem.
This is my code in java:

private static BigInteger LEHMER(BigInteger A0, BigInteger A1) {

BigInteger compareNum = new new BigInteger("9223372036854775808"); //math.pow(2,63)

while( A1.compareTo(compareNum) >= 0) {
int h = A0.bitCount()+1 - 64; //or maybe 63
BigInteger a0 = A0.shiftRight(h);
BigInteger a1 = A1.shiftRight(h);

BigInteger u0 = new BigInteger("1");
BigInteger u1 = new BigInteger("0");
BigInteger v0 = new BigInteger("0");
BigInteger v1 = new BigInteger("1");

break;

BigInteger r = a0.subtract(q0.multiply(a1)); a0 = a1; a1 = r;
r = u0.subtract(q0.multiply(u1)); u0 = u1; u1 = r;
r = v0.subtract(q0.multiply(v1)); v0 = v1; v1 = r;
}

if (v0.equals(BigInteger.ZERO)) {
BigInteger R = A0.remainder(A1); A0 = A1; A1 = R;
}
else {
A0 = R; A1 = T;
}
}

while (A1.compareTo(BigInteger.ZERO) > 0) {
BigInteger R = A0.remainder(A1); A0 = A1; A1 = R;
}

return A0;
}

The basic Euclidean algorithm:

private static BigInteger EA(BigInteger a, BigInteger b) {

while ( !b.equals(BigInteger.ZERO) ) {
BigInteger q = a.divide(b);
BigInteger r = a.subtract(q.multiply(b)); a = b; b = r;
}

return a;
}