Spiegare come funziona il controllo coprime

Question

Ogni volta che utilizzo il metodo Euclid per verificare se due numeri sono co-prime. Ma c'è una soluzione che ha usato questo codice per verificare la presenza di co-primeness, e il tempo impiegato per questo è stato molto più veloce rispetto al metodo di Euclide: (source)

private static boolean isCoprime(long u, long v) { 
    if (((u | v) & 1) == 0) 
     return false; 

    while ((u & 1) == 0) 
     u >>= 1; 
    if (u == 1) 
     return true; 

    do { 
     while ((v & 1) == 0) 
      v >>= 1; 
     if (v == 1) 
      return true; 

     if (u > v) { 
      long t = v; 
      v = u; 
      u = t; 
     } 
     v -= u; 
    } while (v != 0); 

    return false; 
} 

non riesco a capire come questo lavoro. (Capisco operazioni bit per bit). Per esempio, che cosa significano queste righe ...

if (((u | v) & 1) == 0) 
    return false; 

Perché semplicemente restituire falso? Inoltre ci sono altre linee che non sono in grado di capire cosa sta succedendo. Se qualcuno di voi potrebbe semplicemente darmi qualche consiglio, sarà di grande aiuto.

Answer 1

Il codice che hai postato è una modifica dello binary GCD algorithm. Ecco il mio commento commentato:

private static boolean isCoprime(long u, long v) { 
    // If both numbers are even, then they are not coprime. 
    if (((u | v) & 1) == 0) return false; 

    // Now at least one number is odd. Eliminate all the factors of 2 from u. 
    while ((u & 1) == 0) u >>= 1; 

    // One is coprime with everything else by definition. 
    if (u == 1) return true; 

    do { 
     // Eliminate all the factors of 2 from v, because we know that u and v do not have any 2's in common. 
     while ((v & 1) == 0) v >>= 1; 

     // One is coprime with everything else by definition. 
     if (v == 1) return true; 

     // Swap if necessary to ensure that v >= u. 
     if (u > v) { 
      long t = v; 
      v = u; 
      u = t; 
     } 

     // We know that GCD(u, v) = GCD(u, v - u). 
     v -= u; 
    } while (v != 0); 

    // When we reach here, we have v = 0 and GCD(u, v) = current value of u, which is greater than 1. 
    return false; 
}