Java inverse Modulo 2 ** 64

Question

eine ungerade long x, Da ich suche long y so dass ihr Produkt Modulo 2**64 (dh die normale überquell Arithmetik) gleich 1. Um deutlich zu machen, was ich meine: Das könnte sein in ein paar tausend Jahre auf diese Weise berechnet:

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

ich weiß, dass dies den erweiterten euklidischen Algorithmus gelöst werden kann schnell mit, aber es erfordert die Fähigkeit, alle beteiligten Zahlen darzustellen (in einem Bereich bis zu 2**64, so dass auch ohne Vorzeichen Arithmetik würde nicht helfen). Die Verwendung von BigInteger würde sicherlich helfen, aber ich frage mich, ob es einen einfacheren Weg gibt, möglicherweise mit dem erweiterten euklidischen Algorithmus für positive Longs implementiert.

Answer 1

Hier ist eine Möglichkeit, es zu tun. Dies nutzt den erweiterten euklidischen Algorithmus eine inverse von abs(x) Modulo 2 , und am Ende ist es reicht "zu finden, die Antwort bis zu einer inversen Modulo 2 und wendet einen Vorzeichenwechsel, falls erforderlich:

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

fand ich es einfacher, mit 2 als 2 , hauptsächlich zu arbeiten, weil es Probleme mit negativen Zahlen vermeidet: 2 als Java long negativ ist.

Answer 2

In der Zwischenzeit habe ich daran erinnert habe/neu erfunden eine sehr einfache Lösung:

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

es wegen der zwei Dinge funktioniert:

• in jeder Iteration, wenn das entsprechende Bit von product1 ist, dann ist es falsch, und der einzige Weg zu beheben ist, indem Sie das entsprechende Bit y
• kein Bit y beeinflusst alle weniger signifikanten Bit o f product, so dass keine vorherige Arbeit wird
rückgängig gemacht

ich mit int gestartet, da für long es muss auch funktionieren, und für int Ich konnte eine abschließende Prüfung durchführen.

Eine andere Idee: Es muss eine Nummer n>0 so dass x**n == 1 und damit y == x**(n-1). Das sollte wahrscheinlich schneller sein, ich kann mich einfach nicht genug Mathe nennen, um n zu berechnen.