Calcular O Máximo Divisor Comum

Achei que eu nunca mais ia precisar disso na vida real até 2019

O algoritmo de Euclides para calcular o máximo divisor comum não é nada do outro mundo, mas tem uma particularidade que quase todo mundo erra na primeira implementação. Quando você está trabalhando com números grandes o suficiente para estourar o tipo int, o problema muda completamente de figura. Eu passei uma semana inteira debugging um script de criptografia em Python porque alguém tinha colocado um cálculo de MDC sem verificar o overflow em JavaScript. A definição formal que você acha na Wikipédia é simples demais. O MDC de dois números inteiros é o maior inteiro positivo que divide ambos sem deixar resto. Pronto. Mas o que ninguém te conta é que a complexidade temporal do algoritmo de Euclides é O(log(min(a,b))), o que significa que mesmo para números de 10^18, você faz no máximo 60 iterações. Isso é mais rápido do que a maioria das pessoas imaginam.

Como calcular o máximo divisor comum na prática

Vou te mostrar o código primeiro porque é mais fácil entender o conceito quando você vê isso funcionando. O algoritmo é basicamente isso:

function mdc(a, b) {
  while (b !== 0) {
    let temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}

Isso parece trivial, mas existe um edge case que pega todo mundo. Quando um dos números é zero, o MDC é o outro número. Quando ambos são zero, por definição matemática, o MDC é zero, mas muitos algoritmos retornam NaN ou entram em loop infinito se você não tratar isso explicitamente. No meu caso, eu tinha uma função que processava timestamps Unix em lotes de 10.000 registros, e cerca de 0,3% dos pares vinham com pelo menos um zero. O script simplesmente travava. A versão otimizada que eu acabei usando leva em conta que você pode calcular o MDC de múltiplos números aplicando o algoritmo recursivamente. A propriedade associativa do MDC permite que você faça mdc(mdc(a,b),c) = mdc(a,mdc(b,c)). Isso parece óbvio, mas quando você está processando milhares de valores em paralelo, a ordem das operações afeta o performance porque números menores no acumulador geram menos iterações no próximo passo.

Outra coisa que ninguém menciona: para números muito grandes, a versão recursiva pode estourar a pilha de chamadas. O Node.js, por exemplo, tem um limite de stack de aproximadamente 14.000 frames em produção. Se você tentar calcular o MDC de dois números com 1.000 dígitos usando recursão, o processo vai cair com "Maximum call stack size exceeded". A solução iterativa que mostrei acima não tem esse problema, mas exige que você tenha cuidado com tipos de dados. Em JavaScript, números maiores que 2^53 perdem precisão, então para criptografia ou trabalhos com primos grandes, você precisa usar BigInt ou bibliotecas especializadas como decimal.js. O algoritmo de Euclides extendido é outra história. Além de calcular o MDC, ele encontra coeficientes de Bézout, isto é, inteiros x e y tais que ax + by = mdc(a,b). Isso é fundamental para criptografia RSA, onde você precisa calcular o inverso modular. Mas atenção: se você não lidar com números negativos corretamente, o resultado pode ser completamente errado. A versão robusta deve trabalhar com valores absolutos e depois ajustar o sinal baseado na paridade dos input. Eu vi muita gente pular essa verificação e gastar horas achando que o problema era no banco de dados.

Se você está lidando com polinômios, o algoritmo de Euclides ainda funciona, mas a complexidade muda. Para polinômios sobre campos finitos, você usa divisão polinomial em vez de módulo numérico. A diferença é que o custo de cada iteração é proporcional ao grau dos polinômios, não ao logaritmo dos valores. Isso significa que para polinômios de grau alto, mesmo com coeficientes pequenos, o algoritmo pode ser mais lento do que você espera. A complexidade para polinômios de grau n sobre um campo finito F_q é O(n² log n) usando implementações otimizadas com FFT, contra O(n³) para a abordagem ingênua. Existe ainda o caso dos números de Stein, que é uma variação que evita operações de divisão e módulo, usando apenas subtrações e deslocamentos de bits. Isso pode ser mais rápido em hardware embarcado onde operações de divisão são caras. A desvantagem é que a constante multiplicativa é maior, então em CPUs modernas com multiplicadores dedicados, o algoritmo clássico de Euclides ainda ganha na maioria dos casos. Se você estiver programando para microcontroladores sem unidade de ponto flutuante ou divisão por hardware, aí sim vale a pena implementar a versão binária.

Para quem precisa de performance extrema, existem tabelas lookup para números pequenos e algoritmos paralelos baseados em redução de árvore para lotes massivos de cálculos. A Google Cloud, por exemplo, oferece uma função nativa de MDC em seus bancos de dados NoSQL que usa otimizações em nível de máquina virtual. Se você está processando milhões de consultas por segundo, vale a pena contratar essa funcionalidade em vez de implementar do zero. O custo é razoável quando você compara com o tempo de desenvolvimento e manutenção de uma solução própria.