Teoria de números/Eficiência do algoritmo de Euclides
Neste capítulo, será discutido quão eficiente é o algoritmo de Euclides para o cálculo do MDC. De forma mais precisa, se forem dados dois números inteiros:
- Quantas etapas (divisões) do algoritmo são necessárias para que um resto seja zero?
Fazendo estimativas
Recorde-se que o algoritmo baseia-se na construção da sequência:
cujos termos verificam as seguintes igualdades:
1 | |||
2 | |||
k-1 | |||
k | pois |
O algoritmo fornece , que é o último resto não nulo, obtido em passos (divisões).
Uma observação importante é que o resto de uma divisão é sempre menor que a metade do dividendo:
Sendo a primeira desigualdade válida porque e a segunda porque . Deste modo, tem-se
e em geral
- , para cada .
Assim, comparando os termos cujos índices são pares, segue:
Por indução, resulta para cada termo:
De modo análogo, ao comparar os termos ímpares, e usar novamente indução, segue:
Com isso, a sequência dos decresce geometricamente, pois está fixado. O fato de ser uma sequência decrescente já havia sido demonstrado quando se justificou o funcionamento do algoritmo de Euclides. A novidade aqui é a velocidade com que a sequência decresce. Pelos cálculos anteriores, os restos diminuem, no mínimo, tão rápido quanto os termos da progressão geométrica .
A questão colocada era: Quantas divisões são necessárias para que o resto seja zero?
Analisando a progressão geométrica dada anteriormente, conclui-se que algum de seus termos é menor do que . Nesse caso, o resto correspondente será nulo, e o algoritmo para. Para ser mais exato, como
o menor índice inteiro que torna menor que é
Onde denota o maior inteiro que não supera (a parte inteira de ).
Então , e consequentemente , pois os restos são números inteiros não-negativos.
Assim, sabendo que o algoritmo para exatamente quando , conlui-se que tal índice não pode ser maior que , em símbolos:
Para melhor compreender o significado dessa estimativa, considere que tem dígitos decimais. Então:
Aplicando o logaritmo em ambos os membros da segunda desigualdade, resulta
Logo, , que para valores grandes de é aproximadamente .
Embora esta não seja a melhor aproximação para , já é bastante útil, pois mostra que o número de etapas cresce linearmente com o número de dígitos de .
O pior caso
Para obter uma estimativa mais precisa do número de etapas que o algoritmo de Euclides leva para determinar o MDC de dois números, será considerada a seguinte questão:
- Qual é o menor valor de para o qual o algoritmo leva passos?
Veja alguns exemplos utilizando a representação matricial do algoritmo:
Para :
Para :
Para :
É fácil perceber que é mínimo quando os valores forem todos iguais a , cada entrada da matriz é um polinômio nas variáveis (que são positivas), e cujos coeficiêntes são (se puder, acrescente uma justificativa mais formal).
Se cada quociente for substituído por na fórmula de recorrência
Esta passará a ser:
Que vale para satisfazendo .
A nova relação lembra a fórmula que define a sequência de Fibonacci, embora esteja "ao contrário".
Predefinição:Ocultar ao imprimirPredefinição:Somente ao imprimir
Predefinição:FPM-cor Matricialmente, as condições produzem as seguintes igualdades:
- , sendo que .
Com um simples uso do princípio de indução finita, consegue-se:
- , desde que .
Deste modo,
Como , segue que
- Teorema
Dado , sejam e os menores números tais que o algoritmo de Euclides aplicado a e leva exatamente passos, então e .
Exemplificando
Para determinar o valor de , seria necessário efetuar cinco divisões:
Logo, . Aproveitando este exemplo, observe que:
No entanto, se qualquer dos números for menor, o algoritmo requer menos etapas. Por exemplo, ao determinar tem-se:
Donde, .
Já o cálculo de é ainda mais simples:
Portanto, .
Melhorando as estimativas
Sabendo qual é o pior caso para a aplicação do algoritmo de Euclides, pode-se deduzir uma melhor estimativa de sua eficiência. Uma análise mais elaborada que aquela apresentada no início do capítulo fornece o seguinte resultado:
Teorema de Lamé
- Teorema
O número de passos (de divisões) no algoritmo de Euclides com entradas e é limitado superiormente por vezes a quantidade de dígitos decimais em .
Gabriel-Lamé |
Predefinição:FPM-cor Para demonstrar o teorema de Lamé, é importante ter em mente algumas propriedades relacionadas a sequência de Fibonacci e ao número de ouro:
Tem-se:
- , arredondado para o inteiro mais próximo.
Como foi visto anteriormente, quando é exige exatamente passos, é tem-se e . Logo,
Aplicando o logaritmo em ambos os menbros, segue:
ou seja
Mas , então:
- , onde é o número de dígitos de
Demonstração da fórmula de Binet
Nesta seção, será deduzida a fórmula de Binet:
onde e .
A principal razão para se utilizar está fórmula, em vez da definição recursiva da sequência de Fibonacci, é que ela permite a obtenção de um termo da sequência sem precisar calcular os anteriores. Predefinição:Demonstração
Exercícios
- Verifique, utilizando o princípio de indução, que:
- Escreva outra demonstração para a fórmula de Binet, utilizando o princípio de indução.
Por enquanto, não há muitos exercícios sobre este capítulo. O leitor está convidado a adicionar mais ítens a essa seção, para ajudar a melhorar o texto.