5

奇数を考えると、それらの積モジュロ（つまり、通常のオーバーフロー演算を使用）が1に等しくなるようにlong x探しています。意味を明確にするために：これは、この方法で数千年で計算できます。long y2**64

for (long y=1; ; y+=2) {
    if (x*y == 1) return y;
}

これは拡張ユークリッドアルゴリズムを使用してすばやく解決できることは知っていますが、関連するすべての数値を表す機能が必要です（最大で2**64、符号なし算術でも役に立ちません）。使用BigIntegerすることは確かに役立ちますが、正の長さに対して実装された拡張ユークリッドアルゴリズムを使用するなど、より簡単な方法があるのではないかと思います。

4

2 に答える 2

2

その間に、私は非常に単純な解決策を思い出し/再発明しました：

public static int inverseOf(int x) {
    Preconditions.checkArgument((x&1)!=0, "Only odd numbers have an inverse, got " + x);
    int y = 1;
    for (int mask=2; mask!=0; mask<<=1) {
        final int product = x * y;
        final int delta = product & mask;
        y |= delta;
    }
    return y;
}

それは2つの理由で機能します：

  • 各反復で、の対応するビットがでproductある場合1、それは間違っています。修正する唯一の方法は、の対応するビットを変更することです。y
  • の重要度の低いビットにy影響を与えることproductはないため、前の作業が取り消されることはありません

それもうまくいくはずで、徹底的なテストを実行できたintので、私は始めました。longint

別のアイデア：、、したがって。n>0のような数が必要です。これはおそらくもっと速いはずです、私は計算するのに十分な数学を思い出せません。x**n == 1y == x**(n-1)n

于 2012-07-28T17:57:45.303 に答える
1

これを行う1つの方法があります。これは、拡張ユークリッドアルゴリズムを使用して、abs(x)モジュラ2 62の逆数を見つけ、最後に、答えをモジュラ2 64の逆数まで「拡張」し、必要に応じて符号の変更を適用します。

public static long longInverse(long x) {

    if (x % 2 == 0) { throw new RuntimeException("must be odd"); }

    long power = 1L << 62;

    long a = Math.abs(x);
    long b = power;
    long sign = (x < 0) ? -1 : 1;

    long c1 = 1;
    long d1 = 0;
    long c2 = 0;
    long d2 = 1;

    // Loop invariants:
    // c1 * abs(x) + d1 * 2^62 = a
    // c2 * abs(x) + d2 * 2^62 = b 

    while (b > 0) {
        long q = a / b;
        long r = a % b;
        // r = a - qb.

        long c3 = c1 - q*c2;
        long d3 = d1 - q*d2;

        // Now c3 * abs(x) + d3 * 2^62 = r, with 0 <= r < b.

        c1 = c2;
        d1 = d2;
        c2 = c3;
        d2 = d3;
        a = b;
        b = r;
    }

    if (a != 1) { throw new RuntimeException("gcd not 1 !"); }

    // Extend from modulo 2^62 to modulo 2^64, and incorporate sign change
    // if necessary.
    for (int i = 0; i < 4; ++i) {
        long possinv = sign * (c1 + (i * power));
        if (possinv * x == 1L) { return possinv; }
    }

    throw new RuntimeException("failed");
}

主に負の数の問題を回避するため、262よりも262を使用する方が簡単であることがわかりました。Javaはlong負であるため、263です。

于 2012-07-28T17:28:06.073 に答える