método más rápido para determinar si dos números son coprime

Question

Estoy trabajando en un problema matemático que consiste en coprime enteros. Escribí un programa de ordenador que me permite la búsqueda de los números que estoy buscando. Sin embargo estoy buscando en un gran conjunto de los números enteros y tengo que comparar muchos pares de números y determinar si son coprime. Mi programa para hacer esto tantas veces que cualquier reducción en el tiempo de cálculo para cada par de números podrían reducir significativamente el tiempo de ejecución general del programa.

Actualmente estoy usando el algoritmo de Euclides.

http://en.wikipedia.org/wiki/Euclidean_algorithm

Aunque el algoritmo de Euclides es un método muy eficiente, no sé si es el más rápido. No necesito el mcd de dos números acabo de necesidad para determinar si son coprime o no.

Mi pseudocódigo:

mientras que (B ≠ 0)

{T = B

B = a mod T

A = T}

donde a y B son el par de enteros en cuestión y T es una variable ficticia utilizada para mantener un valor a ser utilizado en un posterior cálculo. Para aquellos que no han escrito un programa de ordenador antes, mientras que el proceso en el paréntesis se repite hasta que la condición en el paréntesis es falso. Al final del bucle la variable a se convierte en el mcd de dos enteros. si A=1 los dos números son coprime si a>1, a continuación, los números no son coprime.

Aunque el programa anterior es simple, es un proceso iterativo y estoy en busca de un método que sólo se necesita uno o dos pasos.

Gracias de antemano!

Answer 1

Aquí una versión en C sharp (la más rápida para mí)

 static bool coprime(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;
}