O que é mais eficiente para o GCD?

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

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 $a_i$$b_i$$i$

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 ′ $a'_i$$b'_i$ab$i$

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.$a_i=0$$a'_i=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).

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 .

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.

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.

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 ++)

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.