Máximo divisor comum

"A good algorithm is like a sharp knife:
it does what it is supposed to do with a minimum amount of applied effort.
Using the wrong algorithm to solve a problem is like trying to cut a steak with a screwdriver:
you may eventually get a digestible result,
but you will expend considerably more effort than necessary,
and the result is unlikely to be aesthetically pleasing."
--Th. Cormen, Ch. Leiserson, R. Rivest, Introduction to Algorithms É

Suponha que m e n são números inteiros. Dizemos que n divide m se n > 0 e m % n == 0. Note que,

m % n == 0 se e somente se n > 0 e m = kn para algum inteiro k.

O máximo divisor comum de dois inteiros m e n É o maior inteiro que divide ambos: mdc(m,n) = max{ k | k divide m e k divide n }. É claro que se m == n == 0, então o máximo não faz sentido. Assim, estaremos sempre supondo que pelo menos um dos números dados É não nulo. PROBLEMA: Dados inteiros m e n determinar o máximo dividor comum de m e n (mdc(m,n)). Vamos examinar dois algoritmos para o problema: um óbvio e lento e outro sofisticado e bem mais rápido. Algoritmo óbvio Vamos começar com um algoritmo simples e óbvio: #define min(m,n) ((m) < (n) ? (m) : (n)) long mdc(long m, long n) { int candidato; candidato = min(abs(m),abs(n)); while (m % candidato != 0 || n % candidato != 0) /* 1 */ candidato--; return candidato; } Invariante e correção. Para compreender o funcionamento da função, basta verificar que no início de cada repetição do while, no ponto /* 1 */, vale a seguinte propriedade m % t != 0 ou n % t != 0 para todo t, t >= candidato. Esta propriedade, que pode ser demonstrada por indução (confira!), é dita um invariante do comando while. Deste invariante podemos observar facilmente a correção da função (correção da função = a função funciona). Consumo de tempo. Quantas iterações do while essa função faz? Em outras palavras, quantas vezes o comando "candidato--" é executado? A resposta é min(m,n)-1 no pior caso. (Na presente discussão estamos supondo que m >= 0 e n >= 0.) Neste caso costuma-se dizer que a quantidade de tempo consumida pelo algoritmo, no pior caso, é proporcional a min(m,n), ou ainda, que o tempo gasto pelo algoritmo é da ordem de min(m,n). [A abreviação de "ordem x" é O(x).] Isto significa que o número de operações feitas pela função cresce (no ior caso) como uma função linear de min(m,n). Por exemplo, para a chamada mdc(317811,514229) a função executará 317811 - 1 iterações, pois mdc(317811,514229) == 1 . Ou seja, os inteiros 317811 e 514229 são relativamente primos. &EACUTE; possível resolver o problema fazendo menos operações (isto é, consumindo uma quantidade de tempo menor)? A resposta é SIM. Algoritmo de Euclides O máximo divisor comum entre dois número pode ser determinado através de um algoritmo de 2300 anos (cerca de 300 A.C.), o algoritmo de Euclides. Para calcular o mdc(m,n) para 0 <= n < m, o algoritmo de Euclides usa a seguinte recorrência: mdc(m,0) == m; mdc(m,n) == mdc(n, m % n), para n > 0. Assim, por exemplo, mdc(12,18) == mdc(18,12) == mdc(12,6) == mdc(6,0) == 6. A correção da recorrência proposta por Euclides é baseada no seguinte teorema. Teorema 1 Seja m um inteiro não-negativo e n um inteiro positivo. Para cads inteiro positivo d tem-se que (m % d == 0) e (n % d == 0) se e somente se (n % d == 0) e ((m % n) % d == 0). Exercício: Prove o teorema 1. Eis a implementação recursiva do algoritmo de Euclides para determinar mdc(m,n). long euclides_r(long m, long n) { int i; if (n==0) return m; return euclides_r (n, m % n); } A seqüência abaixo ilustra as chamadas recursivas do algoritmo de Euclides para determinar o mdc de 317811 e 514229: mdc(317811,514229) mdc(514229,317811) mdc(317811,196418) mdc(196418,121393) mdc(121393,75025) mdc(75025,46368) mdc(46368,28657) mdc(28657,17711) mdc(17711,10946) mdc(10946,6765) mdc(6765,4181) mdc(4181,2584) mdc(2584,1597) mdc(1597,987) mdc(987,610) mdc(610,377) mdc(377,233) mdc(233,144) mdc(144,89) mdc(89,55) mdc(55,34) mdc(34,21) mdc(21,13) mdc(13,8) mdc(8,5) mdc(5,3) mdc(3,2) mdc(2,1) mdc(1,0) mdc de 317811 e 514229 e' 1. Quanto tempo o algoritmo leva para parar? Este tempo é certamente proporcional ao número de chamadas recursivas. Suponha que a função euclides_r faz k chamadas recursivas e que no início da 1a. chamada ao algoritmo tem-se que 0 < n <= m. Sejam (m,n) == (m₀,n₀), (m₁,n₁), (m₂,n₂), ... , (m_k,n_k) == (mdc(m,n),0), os valores do par de parâmetros (m,n) no início de cada uma das chamadas da função. Por exemplo, para m==514229 e n==317811 tem-se (m₀,n₀) == (514229,317811), (m₁,n₁) == (317811,196418), ... , (m₂₇,n₂₇) == (1,0), Estimaremos o valor de k em função de m e n. Note que m_i+1 == n_i e n_i+1 == m_i % n_i para i=1,2,...,k. Note ainda que para inteiros a e b, 0 < b <= a vale que a % b < a/2 (verifique!). Desta forma tem-se que m₂ == n₁ == m₀ % n₀ == m % n < m/2¹ m₄ == n₃ == m₂ % n₂ < m₂/2 < m/4 == m/2² m₆ == n₅ == m₄ % n₄ < m₄/2 < m/8 == m/2³ m₈ == n₇ == m₆ % n₆ < m₆/2 < m/16 == m/2⁴ m₁₀ == n₉ == m₈ % n₈ < m₈/2 < m/32 == m/2⁵ ... ... ... Percebe-se que depois de cada 2 chamadas recursivas o valor do primeiro parâmetro cai de pelo menos metade. Assim, quando k é tal que 2^k/2 <= m < 2^(k/2)+1 o valor de m_k é menor que m/2^k/2 == 1 e o algoritmo pára depois de no máximo mais uma chamada recursiva. Logo, o número k de chamadas recursivas é limitado por 2 log₂(m) + 1 , quando 0 < n <= m e por 2 log₂(m) + 2 , quando 0 < m < n, o que é muito melhor que as min(m,n) iterações do algoritmo óbvio. Para o exemplo acima, onde m==317811 e n==514229, 2 log₂(m) + 2 == 2 * 18 + 2 == 38 e o número de chamadas recursivas por euclides_r(317811,514229)feitas foram 28. t (int) log(t) 4 2 5 2 6 2 10 3 64 6 100 6 128 7 1000 9 1024 10 1000000 19 Resumindo, a quantidade de tempo consumida pelo algoritmo de Euclides é, no pior caso, proporcional a log (min(m,n)) Números de Fibonacci e o algoritmo de Euclides Os 10 primeiros números da seqüência de Fibonacci são: 0 1 2 3 4 5 6 7 8 9 10 0 1 1 2 3 5 8 13 21 34 55 Os números de Fibonacci são definidos (ou podem ser calculados) pela seguinte função recursiva: long fibonacci(long n) { if (n == 0) return 0; if (n == 1) return 1; return fibonacci(n-1) + fibonacci(n-2); } Os números de Fibonacci estão intimamente relacionados com o algoritmo de Euclides, como mostra o exercício abaixo. Exercício: Se m > n >= 0 e se a chamada euclides_r(m,n) faz k >=1 chamadas recursivas, então m >= fibonacci(k+2) e n >= fibonacci(k+1). [Sugestao: demonstre por indução em k.] Uma conseqüência imediata deste exercício é Para todo inteiro k > 0, se m > n >= 0 e n < fibonacci(k+1), então a chamada euclides_r(m,n) faz menos de k chamadas recursivas. Por exemplo, fibonacci(28) == 317811 e fibonacci(29) = 514229 e a chamada euclides_r(514229,317811) faz 27 chamadas recursivas. Na verdade, números de Fibonacci consecutivos são os que dão mais trabalho para o algoritmo de Euclides. Exercício: A chamada euclides_r(fibonacci(k+1),fibonacci(k)) faz k-1 chamadas recursivas. [Sugestao: demonstre por indução em k.] Exercícios Estes exercícios se referem à versão limpa de buscabinaria descrita na seção anterior. Prove que para inteiros m, k e n mdc(m,n) == mdc(m + kn, n). Prove que números de Fibonacci consecutivos são relativamente primos. Ë verdade que para todo m >= n > 0 a função mdc faz um número de iterações (do comando while) maior ou igual ao feito (pelo comando do ... while) pela função euclides_i abaixo. long euclides_i(long m, long n) { long r; do { r = m % n; m = n; n = r; } while (r != 0); return m; } Qual função consome uma quantidade maior de memória, euclides_r ou euclides_i? Faça uma estimativa da quantidade de memória consumida por cada uma dessas funções. Matematicamente falando, quanto é 7 % -3? Qual é o valor que o computador devolve? Last modified: Mon Aug 20 11:16:34 BRST 2001

`t`	`(int)` `log(t)`
`4`	`2`
`5`	`2`
`6`	`2`
`10`	`3`
`64`	`6`
`100`	`6`
`128`	`7`
`1000`	`9`
`1024`	`10`
`1000000`	`19`

`0`	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`8`	`9`	`10`
0	1	1	2	3	5	8	13	21	34	55