Java binary method for GCD infinate loop

Question

I'm using the Binary Method to calculate the GCD of two fractions, the method works perfectly fine, except for when I subtract certain numbers from each other.

I'm assuming it's because, for instance, when I subtract 2/15 from 1/6, the GCD has a repeating number or something like that, though I could be wrong.

        //The following lines calculate the GCD using the binary method

        if (holderNum == 0) 
        {
            gcd = holderDem;
        }
        else if (holderDem == 0) 
        {
            gcd = holderNum;
        }
        else if ( holderNum == holderDem)
        {
            gcd = holderNum;
        }

        // Make "a" and "b" odd, keeping track of common power of 2.
        final int aTwos = Integer.numberOfTrailingZeros(holderNum);
        holderNum >>= aTwos;
        final int bTwos = Integer.numberOfTrailingZeros(holderDem);
        holderDem >>= bTwos;
        final int shift = Math.min(aTwos, bTwos);

        // "a" and "b" are positive.
        // If a > b then "gdc(a, b)" is equal to "gcd(a - b, b)".
        // If a < b then "gcd(a, b)" is equal to "gcd(b - a, a)".
        // Hence, in the successive iterations:
        //  "a" becomes the absolute difference of the current values,
        //  "b" becomes the minimum of the current values.
        if (holderNum != gcd)
        {
            while (holderNum != holderDem) 
            {
                    //debuging
                    String debugv3 = "Beginning GCD binary method";
                    System.out.println(debugv3);
                    //debugging
                    final int delta = holderNum - holderDem;
                    holderNum = Math.min(holderNum, holderDem);
                    holderDem = Math.abs(delta);

                    // Remove any power of 2 in "a" ("b" is guaranteed to be odd).
                    holderNum >>= Integer.numberOfTrailingZeros(holderNum);
                    gcd = holderDem;
            }
        }           

        // Recover the common power of 2.
        gcd <<= shift;

That is the code that I'm using to complete this operation, the debugging message prints out forever.

Is there a way to cheat out of this when it gets stuck, or maybe set up an exception?

Answer 1

The problem is with negative values — when one of them is negative, holderNum will always take on the negative value (being the min); holderDem will become postive, so delta equal to a negative less a positive equals a lesser negative. Then holderDem = abs(delta) is a greater positive and keeps increasing. You should take the absolute value of both of them before entering the loop.

E.g.:

holderNum = -1 and holderDem = 6
Iteration 1:

delta = holderNum - holderDem = -1 - 6 = -7
holderNum = Math.min(holderNum, holderDem) = Math.min(-1, 6) = -1
holderDem = Math.abs(delta) = Math.abs(-7) = 7

Iteration 2:

delta = holderNum - holderDem = -1 - 7 = -8
holderNum = Math.min(holderNum, holderDem) = Math.min(-1, 7) = -1
holderDem = Math.abs(delta) = Math.abs(-7) = 8

etc., etc., etc.