Java求2**64的模反元素

Question

给定一个奇数long x，我要找到一个long y，使得它们的乘积在模2**64下等于1（即使用常规溢出算术）。为了明确我的意思：这样可以通过以下方式计算几千年：

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

我知道可以使用扩展欧几里得算法快速解决这个问题，但需要能够表示涉及的所有数字（范围高达2**64，因此即使使用无符号算术也无济于事）。使用BigInteger肯定会有帮助，但我想知道是否有一种更简单的方法，可能是使用针对正长整型实现的扩展欧几里得算法。

- maaartinus

---

Hacker's Delight（黑客的乐趣）建议使用模2^32的算法。我会尝试一些变体，当然要进行大量测试。（也许这值得包含在Guava中...） - Louis Wasserman

@Louis Wasserman：不错的链接...与此同时，我认为我已经得到了一个3倍快的东西——稍后我会发布我的结果。顺便说一下，我需要pow(long, long)（在LongMath中缺失）来实现一种方法。 - maaartinus

pow(long, long)故意被省略，因为将任何东西提高到一个不适合于int的幂次方基本上保证会溢出。（虽然我猜这正是你想要的。） - Louis Wasserman

是的。对于像checkedPow或saturatedPow这样的东西，我同意长指数没有意义，但对于pow，我不这么认为。我已经发布了6种不同解决方案的基准测试和测试。关于Guava，我建议包括来自链接的Math64的内容。 - maaartinus

我们最终采用的规则是假设您不想故意引起溢出。pow和checkedPow之间的区别不在于是否预期会溢出，而在于您是否想要支付检查的开销。 - Louis Wasserman

Answer 1

这是一种实现方式。它使用扩展欧几里得算法来找到模2^62下abs(x)的逆元，最后将答案“扩展”到模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");
}

我发现使用2⁶²比2⁶³更容易处理，主要是因为它避免了负数问题：在Java中，2⁶³作为long类型是负数。

- Luke Woodward

---

我已经接受了你的解决方案，因为你对我的评论导致了最快的解决方案，请看这里。 - maaartinus

Answer 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;
}

它之所以有效是因为两个原因:

• 在每次迭代中，如果product的相应位为1，那么它是错误的，唯一的修复方式是更改y的相应位。
• 没有y的任何位影响product的任何较低有效位，因此不会撤消任何先前的工作。

我从int开始，因为对于long也必须有效，并且对于int，我可以运行详尽的测试。

另一个想法： 必须有一个大于0的数字n>0，使得x ** n == 1，因此y == x **(n-1)。这可能更快，我只是无法回想起足够的数学来计算n。

- maaartinus

---

+1 有趣的答案。我认为你提到的n的值是2**62。 - Luke Woodward

@Luke Woodward：使用欧拉函数我得到了2**63，但是似乎使用2**62也可以。而且这似乎是最快的方法。 - maaartinus