CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3

Hybrid View

  1. #1
    Join Date
    Apr 2013
    Posts
    1

    Lehmer gcd algorithm

    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 BigInteger("4294967296"); //4294967296 = math.pow(2,32)

    while( A1.compareTo(compareNum) >= 0) {
    int h = A0.bitCount()+1 - 32;
    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
    Join Date
    Jul 2021
    Posts
    1

    Re: Lehmer gcd algorithm

    Hi,
    Looks good.
    Seems, for u0, u1, v0, v1 you do not need to use BigInteger type, just use primitive int (unsigned?) or long (you may extract 63 bits in this case).

  3. #3
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Hanover Germany
    Posts
    20,095

    Re: Lehmer gcd algorithm

    Well, good reply on the question asked more than eight years back!
    Victor Nijegorodov

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured