0

バイナリ法を使用して 2 つの分数の GCD を計算しています。この方法は、特定の数値を互いに減算する場合を除いて、完全に正常に機能します。

たとえば、1/6 から 2/15 を引くと、GCD には繰り返し数などがあるためだと思いますが、間違っている可能性もあります。

        //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;

これは、この操作を完了するために使用しているコードです。デバッグ メッセージは永久に出力されます。

スタックしたときにこれを回避する方法はありますか、または例外を設定する方法はありますか?

4

1 に答える 1

1

問題は負の値の場合です。そのうちの 1 つが負の場合、holderNum常に負の値 (最小値) になります。holderDemはプラスになるのでdelta、マイナスからプラスを引いたものは、マイナスを小さくしたものに等しくなります。その後holderDem = abs(delta)、よりポジティブになり、増加し続けます。ループに入る前に、両方の絶対値を取得する必要があります。

例えば：

holderNum = -1およびholderDem = 6
反復 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

反復 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

などなど

于 2013-06-04T20:35:57.467 に答える