Java inversa módulo 2 ** 64

Question

dado una extraña long x, estoy buscando long y tal que su módulo de productos 2**64 (es decir, utilizando la aritmética desbordante normal) es igual a 1. Para poner en claro lo que quiero decir: Esto podría ser calculado en unos pocos miles de años de esta manera:

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

sé que esto puede ser resuelto rápidamente usando el algoritmo de Euclides extendido, pero se requiere la capacidad de representar todos los números involucrados (que van hasta 2**64, por lo que incluso sin firmar la aritmética no ayudaría). Usar BigInteger seguramente ayudaría, pero me pregunto si hay una manera más simple, posiblemente usando el algoritmo euclidiano extendido implementado para longs positivos.

Answer 1

Aquí hay una manera de hacerlo. Esto utiliza el algoritmo de Euclides extendido a encontrar una inversa de abs(x) módulo 2 , y al final se 'extiende' la respuesta hasta un módulo inversa 2 y aplica un cambio de signo si es necesario:

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"); 
} 

me pareció más fácil trabajar con 2 de 2 , sobre todo porque evita problemas con los números negativos: 2 como Java long es negativo.

Answer 2

Mientras tanto he recordado/reinventado una solución muy simple:

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

Funciona debido a dos cosas:

• en cada iteración si el bit correspondiente de product es 1, entonces está mal, y la única forma de arreglarlo es cambiando el bit correspondiente de y
• ningún bit de y influye en cualquier bit menos significativo o f product, por lo que no se deshace el trabajo previo

Empecé con int ya que para long debe trabajar también, y para int que podría correr una prueba exhaustiva.

Otra idea: debe haber un número n>0 tal que x**n == 1, y por lo tanto y == x**(n-1). Esto probablemente debería ser más rápido, simplemente no puedo recordar suficientes operaciones matemáticas para calcular n.