Java逆模2 ** 64 [英] Java inverse modulo 2**64

问题描述

给出一个奇数的long x，我正在寻找long y，以使它们的乘积2**64(即，使用正常的溢出算法)等于1.在几千年内以这种方式:

Given an odd long x, I'm looking for long y such that their product modulo 2**64 (i.e., using the normal overflowing arithmetic) equals to 1. To make clear what I mean: This could be computed in a few thousand year this way:

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

我知道可以使用扩展的欧几里得算法快速解决此问题，但是它需要能够表示所有涉及的数字(范围为2**64，因此即使无符号算术也无济于事).使用BigInteger肯定会有所帮助，但我想知道是否有更简单的方法，可能使用为正的多头实现的扩展的欧几里得算法.

I know that this can be solved quickly using the extended Euclidean algorithm, but it requires the ability to represent all the involved numbers (ranging up to 2**64, so even unsigned arithmetic wouldn't help). Using BigInteger would surely help, but I wonder if there's a simpler way, possibly using the extended Euclidean algorithm implemented for positive longs.

推荐答案

这是一种方法.它使用扩展的欧几里得算法找到abs(x)模2 ⁶² 的逆，最后将答案扩展"到模2的逆2 ⁶⁴ ，然后必要时应用标志更改:

Here's one way of doing it. This uses the extended Euclidean algorithm to find an inverse of abs(x) modulo 2⁶², and at the end it 'extends' the answer up to an inverse modulo 2⁶⁴ and applies a sign change if necessary:

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 ⁶³ 容易，这主要是因为它避免了负数的问题:2 ⁶³ 作为一个负数. Java long为负.

I found it easier to work with 2⁶² than 2⁶³, mainly because it avoids problems with negative numbers: 2⁶³ as a Java long is negative.

这篇关于Java逆模2 ** 64的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！