Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: need help with lehmer's gcd algorithm code

  1. #1
    Junior Member
    Join Date
    Apr 2013
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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");

    while( !a1.add(u1).equals(BigInteger.ZERO) &&
    !a1.add(v1).equals(BigInteger.ZERO)) {

    BigInteger q0 = a0.add(u0).divide(a1.add(u1));

    if (!q0.equals(a0.add(v0).divide(a1.add(v1))))
    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 {
    BigInteger R = u0.multiply(A0).add(v0.multiply(A1));
    BigInteger T = u1.multiply(A0).add(v1.multiply(A1));
    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;
    }


    Thank you for your help!


  2. #2
    Junior Member
    Join Date
    Apr 2013
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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");

    while( !a1.add(u1).equals(BigInteger.ZERO) &&
    !a1.add(v1).equals(BigInteger.ZERO)) {

    BigInteger q0 = a0.add(u0).divide(a1.add(u1));

    if (!q0.equals(a0.add(v0).divide(a1.add(v1))))
    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 {
    BigInteger R = u0.multiply(A0).add(v0.multiply(A1));
    BigInteger T = u1.multiply(A0).add(v1.multiply(A1));
    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;
    }


    Thank you for your help!

Similar Threads

  1. algorithm to c code
    By shenaz in forum Java Theory & Questions
    Replies: 9
    Last Post: March 18th, 2013, 06:46 AM
  2. Euclid Calculator GCD and LCM using BigInteger
    By Exiled in forum What's Wrong With My Code?
    Replies: 7
    Last Post: November 18th, 2012, 11:00 PM
  3. Java code for Leader's algorithm
    By raj_k in forum Member Introductions
    Replies: 1
    Last Post: August 9th, 2011, 07:20 AM