Teoria de números/Eficiência do algoritmo de Euclides

Origem: Wikilivros, livros abertos por um mundo aberto.

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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".


Este módulo tem a seguinte tarefa pendente: Conferir se o expoente k+1 está correto ou se deveria ser k, na próxima equação

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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é[editar | editar código-fonte]

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é
Este módulo tem a seguinte tarefa pendente: Incluir breve biografia sobre Lamé.

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:

Demonstração
A verificação é direta, exigindo cálculos bastante simples.
  • , arredondado para o inteiro mais próximo.
Demonstração
Utilizando a fórmula de Binet, basta observar que o módulo de é menor que , e consequentemente, quando , tem-se
Demonstração
A justificativa será dada por indução:
  1. Se for verdade que , então:
Demonstração
De fato, valem as seguintes equivalências:

Mas (verifique a partir de ), e pois

Sendo que esta última desigualdade é verdadeira.

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[editar | editar código-fonte]

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.

Demonstração
A relação entre os termos da sequência pode ser descrita matricialmente da seguinte forma:

Para simplificar, será adotada a seguinte notação:

A partir de um simples argumento de indução (veja exercício 1), obtem-se:

Neste ponto, recorre-se à Álgebra linear, para obter um jeito simples de calcular o produto acima. Se puder ser escrito

, com e sendo auto-vetores de , ou seja, vetores não nulos tais que e , será possível obter:

A partir daí será bastante simples conseguir a fórmula explicita para (a segunda componente do vetor à esquerda), pois seriam constantes.

É, portanto, necessário determinar essas constantes, a começar pelos auto-valores de . Tem-se:

Logo , ou seja, Assim, (que implica ) ou . O primeiro caso não é de interesse, pois auto-vetores não são nulos.

Note que a equação acima possui duas raízes:

Além disso, se é raiz da equação, então para cada , o vetor

é um auto-vetor de .

Em particular, se , os auto-vetores correspondentes a cada raiz da equação quadrática são:

De modo que e

Resta escrever conforme se pretendia. Isso é fácil, já que são conhecidos e :

Da segunda equação, segue que . Substituindo esse valor na primeira equação, resulta:

Como (verifique!), tem-se . Logo, .

Assim, . Em consequência:

Em particular, escrevendo a igualdade entre as segundas coordenadas desses vetores, obtem-se a fórmula desejada:

Exercícios[editar | editar código-fonte]

  1. Verifique, utilizando o princípio de indução, que:
  2. 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.