O que é mais eficiente para o GCD?

26

Eu sei que o algoritmo de Euclides é o melhor para obter o GCD (ótimo divisor comum) de uma lista de números inteiros positivos. Mas, na prática, você pode codificar esse algoritmo de várias maneiras. (No meu caso, decidi usar Java, mas C / C ++ pode ser outra opção).

Eu preciso usar o código mais eficiente possível no meu programa.

No modo recursivo, você pode escrever:

static long gcd (long a, long b){
    a = Math.abs(a); b = Math.abs(b);
    return (b==0) ? a : gcd(b, a%b);
  }

E no modo iterativo, fica assim:

static long gcd (long a, long b) {
  long r, i;
  while(b!=0){
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}

Há também o algoritmo binário para o GCD, que pode ser codificado da seguinte maneira:

int gcd (int a, int b)
{
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}
jonaprieto
fonte
3
Eu acho que isso é muito subjetivo e talvez até mais adequado para o StackOverflow. "Mais eficiente, na prática," depende de muitos factores (mesmo imprevisíveis), tal como o architechture subjacente, hierarquia de memória, tamanho e forma da entrada etc
Juho
5
Este é o mesmo algoritmo expresso de maneira recursiva e iterativa. Eu acho que a diferença deles é insignificante, uma vez que o algoritmo Euclid converge bastante rápido. Escolha um que atenda às suas preferências.
pad
6
Você pode tentar criar um perfil desses dois. Como a versão recursiva é uma chamada final, não é improvável que o compilador emita quase o mesmo código.
Louis
11
isto está errado. deve ser while b! = 0 e, em seguida, retorne a. Caso contrário, a divisão será zerada. também não use recursão se você tiver realmente grandes gcds ... você obtém uma pilha de estados de pilha e função ... por que não apenas iterar?
precisa
4
Observe que existem algoritmos GCD assintoticamente mais rápidos. Por exemplo, en.wikipedia.org/wiki/Binary_GCD_algorithm
Neal Young

Respostas:

21

Seus dois algoritmos são equivalentes (pelo menos para números inteiros positivos, o que acontece com números inteiros negativos na versão imperativa depende da semântica de Java pela %qual eu não conheço de cor). Na versão recursiva, deixar e b i ser o argumento do i th chamada recursiva: um i + 1 = b i b i + 1 = um i m o d b iumaEubEuEu

umaEu+1 1=bEubEu+1 1=umaEumodbEu

Na versão imperativo, deixa e b ' i ser os valores das variáveis e no início do i th iteração do loop. a i + 1 = b i b i + 1 = a i m o d b iumaEubEuabEu

umaEu+1 1=bEubEu+1 1=umaEumodbEu

Percebe uma semelhança? Sua versão imperativa e sua versão recursiva estão calculando exatamente os mesmos valores. Além disso, ambos final, ao mesmo tempo, quando (resp. De uma ' i = 0 ), de modo que executam o mesmo número de iterações. Então, algoritmicamente falando, não há diferença entre os dois. Qualquer diferença será uma questão de implementação, altamente dependente do compilador, do hardware em que é executado e, possivelmente, do sistema operacional e de quais outros programas estão sendo executados simultaneamente.umaEu=0 0umaEu=0 0

A versão recursiva faz apenas chamadas recursivas de cauda . A maioria dos compiladores para linguagens imperativas não os otimiza e, portanto, é provável que o código que eles gerem gaste um pouco de tempo e memória construindo um quadro de pilha a cada iteração. Com um compilador que otimiza chamadas de cauda (compiladores para linguagens funcionais quase sempre o fazem), o código de máquina gerado pode muito bem ser o mesmo para ambos (supondo que você harmonize essas chamadas para abs).

Gilles 'SO- parar de ser mau'
fonte
8

Para números pequenos, o algoritmo GCD binário é suficiente.

O GMP, uma biblioteca bem mantida e testada no mundo real, mudará para um algoritmo especial de meio GCD após passar um limite especial, uma generalização do algoritmo de Lehmer. Lehmer usa multiplicação de matrizes para aprimorar os algoritmos euclidianos padrão. De acordo com os documentos, o tempo de execução assintótico do HGCD e do GCD é O(M(N)*log(N))onde M(N)é o tempo para multiplicar dois números de membros N.

Detalhes completos sobre seu algoritmo podem ser encontrados aqui .

qwr
fonte
O link realmente não fornece detalhes completos e nem define o que é um "membro" ...
einpoklum - reinstala Monica
2

Como eu sei, Java não suporta otimização de recursão de cauda em geral, mas você pode testar sua implementação Java; se não o suporta, um forloop simples deve ser mais rápido; caso contrário, a recursão deve ser igualmente rápida. Por outro lado, essas são otimizações de bits, escolha o código que achar mais fácil e mais legível.

Devo também observar que o algoritmo GCD mais rápido não é o algoritmo de Euclid, o algoritmo de Lehmer é um pouco mais rápido.

PJTraill
fonte
Você quer dizer , tanto quanto eu sei ? Você quer dizer que a especificação de linguagem não exige essa otimização (seria surpreendente se exigisse) ou que a maioria das implementações não a implementa?
PJTraill 25/05
1

Primeiro, não use recursividade para substituir um loop apertado. Está lento. Não confie no compilador para otimizá-lo. Segundo, no seu código, você chama Math.abs () em todas as chamadas recursivas, o que é inútil.

No seu loop, você pode facilmente evitar variáveis ​​temporárias e trocar aeb o tempo todo.

int gcd(int a, int b){
    if( a<0 ) a = -a;
    if( b<0 ) b = -b;
    while( b!=0 ){
        a %= b;
        if( a==0 ) return b;
        b %= a;
    }
    return a;
}

Trocar usando a ^ = b ^ = a ^ = b reduz a fonte, mas requer muitas instruções para executar. Será mais lento que o swap chato com uma variável temporária.

Florian F
fonte
3
“Evite recursividade. É lento ”- apresentado como conselho geral, isso é falso. Depende do compilador. Geralmente, mesmo com compiladores que não otimizam a recursão, não é lento, apenas consome pilhas.
Gilles 'SO- stop be evil'
3
Mas para códigos curtos como esse, a diferença é significativa. Consumo de pilha significa escrever e ler da memória. Isso é lento. O código acima é executado em 2 registros. Recursividade também significa fazer chamadas, que são mais longas que um salto condicional. Uma chamada recursiva é muito mais difícil para a previsão de ramificação e mais difícil para alinhar.
Florian F
-2

Para números pequenos ,% é uma operação bastante cara, talvez a mais simples recursiva

GCD[a,b] := Which[ 
   a==b , Return[a],
   b > a, Return[ GCD[a, b-a]],
   a > b, Return[ GCD[b, a-b]]
];

é mais rápido? (Desculpe, código do Mathematica e não C ++)

Per Alexandersson
fonte
Não parece certo. Para b == 1, ele deve retornar 1. E o GCD [2,1000000000] ficará lento.
Florian F
Ah, sim, eu cometi um erro. Fixo (acho) e esclarecido.
Por Alexandersson
Normalmente, o GCD [a, 0] também deve retornar a. Seus laços para sempre.
Florian F
Estou com voto negativo, pois sua resposta contém apenas código. Gostamos de focar nas idéias deste site. Por exemplo, por que% é uma operação cara? Especular um pedaço de código não é realmente uma boa resposta para este site, na minha opinião.
Juho
11
Penso que a ideia de que o módulo é mais lento que a subtração pode ser considerada folclore. Ele é válido tanto para números inteiros pequenos (subtração geralmente leva um ciclo, o módulo raramente) como para números inteiros grandes (subtração é linear, não sei qual é a melhor complexidade para o módulo, mas é definitivamente pior do que isso). Obviamente, você também precisa considerar o número de iterações necessárias.
Gilles 'SO- stop be evil'
-2

O algoritmo Euclid é mais eficiente para calcular o GCD:

MDC longo estático (longo a, longo b)
{
se (b == 0)
retornar a;
outro
retorno mcd (, a% b);
}

exemplo:-

Seja A = 16, B = 10.
GCD (16, 10) = GCD (10, 16% 10) = GCD (10, 6)
GCD (10, 6) = GCD (6, 10% 6) = GCD (6, 4)
GCD (6, 4) = GCD (4, 6% 4) = GCD (4, 2)
GCD (4, 2) = GCD (2, 4% 2) = GCD (2, 0)


Como B = 0, o GCD (2, 0) retornará 2. 
Rohit-Pandey
fonte
4
Isso não responde à pergunta. O solicitante apresenta duas versões do Euclid e pergunta qual é o mais rápido. Parece que você não percebeu isso e apenas declara a versão recursiva como o único algoritmo de Euclides, e afirma sem nenhuma evidência de que seja mais rápido que todo o resto.
David Richerby