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?

Índice

1 Fazendo estimativas
2 O pior caso
- 2.1 Exemplificando
3 Melhorando as estimativas
- 3.1 Teorema de Lamé
4 Demonstração da fórmula de Binet
5 Exercícios

[editar] Fazendo estimativas

Recorde-se que o algoritmo baseia-se na construção da sequência:

$a = r_0 \ge b = r_1 > r_2 > \ldots > r_k > r_{k+1} = 0\,\!$

cujos termos verificam as seguintes igualdades:

1	$r_0 =\,\!$	$r_1q_0+r_2\,\!$	$0 \le r_2<r_1\,\!$
2	$r_1 =\,\!$	$r_2q_1+r_3\,\!$	$0 \le r_3<r_2\,\!$
	$\vdots\,\!$
k-1	$r_{k-2} =\,\!$	$r_{k-1}q_{k-2}+r_{k}\,\!$	$0 \le r_{k}<r_{k-1}\,\!$
k	$r_{k-1} =\,\!$	$r_{k}q_{k-1}+r_{k+1} = r_{k}q_{k-1}\,\!$	pois $0 = r_{k+1}<r_{k}\,\!$

O algoritmo fornece $(a,b) = r_k\,\!$ , que é o último resto não nulo, obtido em $k\,\!$ passos (divisões).

Uma observação importante é que o resto de uma divisão é sempre menor que a metade do dividendo:

$r_0 = r_1q_0+r_2 \ge r_1+r_2 > 2r_2\,\!$

Sendo a primeira desigualdade válida porque $q_0\ge 1\,\!$ e a segunda porque $r_1>r_2\,\!$ . Deste modo, tem-se

$r_0 > 2r_2\,\!$

$r_1 > 2r_3\,\!$

$r_2 > 2r_4\,\!$

$r_3 > 2r_5\,\!$

e em geral

$r_{k}>2r_{k+2}\,\!$ , para cada $k\ge 0\,\!$ .

Assim, comparando os termos cujos índices são pares, segue:

$r_{0}<a/2\,\!$

$r_{2}<r_{0}/2<a/4\,\!$

$r_{4}<r_{2}/2<r_{0}/4<a/8\,\!$

$\ldots\,\!$

A Wikipédia tem mais sobre este assunto:

Progressão geométrica#Progressão geométrica decrescente

Por indução, resulta para cada termo:

$r_{2j}<a/2^{j+1}\,\!$

De modo análogo, ao comparar os termos ímpares, e usar novamente indução, segue:

$r_{2j+1}<a/2^{j+1}\,\!$

Com isso, a sequência dos $r_j\,\!$ decresce geometricamente, pois $a\,\!$ 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,\frac{a}{2}, \frac{a}{4}, \frac{a}{8}, \frac{a}{16}, \ldots )\,\!$ .

A questão colocada era: Quantas divisões são necessárias para que o resto $r_{k+1}\,\!$ seja zero?

Analisando a progressão geométrica dada anteriormente, conclui-se que algum de seus termos é menor do que $1\,\!$ . Nesse caso, o resto correspondente será nulo, e o algoritmo para. Para ser mais exato, como

$\frac{a}{2^{x}} < 1 \Leftrightarrow a < 2^{x} \Leftrightarrow \log_2 a < x \,\!$

o menor índice inteiro $t\,\!$ que torna $\frac{a}{2^t}\,\!$ menor que $1\,\!$ é

$t = \lfloor \log_2 a \rfloor + 1\,\!$

Onde $\lfloor \alpha \rfloor\,\!$ denota o maior inteiro que não supera $\alpha\,\!$ (a parte inteira de $\alpha\,\!$ ).

Então $r_{2t} < \frac{a}{2^{t+1}} < \frac{a}{2^{t}} < 1\,\!$ , e consequentemente $r 2 t = 0$ , pois os restos são números inteiros não-negativos.

Assim, sabendo que o algoritmo para exatamente quando $r_{k+1} = 0\,\!$ , conlui-se que tal índice $k+1\,\!$ não pode ser maior que $2t\,\!$ , em símbolos:

$k+1 \le 2(\lfloor \log_2 a \rfloor + 1)\,\!$

Para melhor compreender o significado dessa estimativa, considere que $a\,\!$ tem $N\,\!$ dígitos decimais. Então:

$10^{N-1}\le a < 10^N\,\!$

Aplicando o logaritmo em ambos os membros da segunda desigualdade, resulta

$\log_2 a < N\cdot\log_2 10\,\!$

Logo, $k+1 \le 2 (\lfloor\log_2 a\rfloor +1)< 2N\cdot\log_2 10 + 2\,\!$ , que para valores grandes de $N\,\!$ é aproximadamente $6,6N\,\!$ .

Embora esta não seja a melhor aproximação para $k\,\!$ , já é bastante útil, pois mostra que o número de etapas cresce linearmente com o número de dígitos de $a\,\!$ .

[editar] 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 $a\,\!$ para o qual o algoritmo leva $n\,\!$ passos?

Veja alguns exemplos utilizando a representação matricial do algoritmo:

Para $n=1\,\!$ :

$\begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} q_0 & 1\\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} d \\ 0 \end{bmatrix}\,\!$

Para $n=2\,\!$ :

$\begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} q_0 & 1\\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} q_1 & 1\\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} d \\ 0 \end{bmatrix} = \begin{bmatrix} q_0q_1+1 & q_0\\ q_1 & 1 \end{bmatrix} \cdot \begin{bmatrix} d \\ 0 \end{bmatrix}\,\!$

Para $n=3\,\!$ :

$\begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} q_0q_1+1 & q_0\\ q_1 & 1 \end{bmatrix} \cdot \begin{bmatrix} q_2 & 1\\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} d \\ 0 \end{bmatrix} = \begin{bmatrix} q_0q_1q_2+q_0+q_2 & q_0q_1+1\\ q_1 & 1 \end{bmatrix} \begin{bmatrix} d \\ 0 \end{bmatrix}\,\!$

É fácil perceber que $a\,\!$ é mínimo quando os valores $q_0,\ldots, q_{k-1} \,\!$ forem todos iguais a $1\,\!$ , cada entrada da matriz é um polinômio nas variáveis $q_j\,\!$ (que são positivas), e cujos coeficiêntes são $1\,\!$ (se puder, acrescente uma justificativa mais formal).

Se cada quociente for substituido por $1\,\!$ na fórmula de recorrência

$r_{j-1} = r_jq_{j-1} + r_{j+1}\,\!$

Esta passará a ser:

$r_{j-1} = r_j + r_{j+1}\,\!$

Que vale para $j\,\!$ satisfazendo $1\le j\le k\,\!$ .

A nova relação lembra a fórmula que define a sequência de Fibonacci, embora esteja "ao contrário".

Recordando

A sequência de fibonacci é definida pelas seguintes equações:

$F_0 = 0\,\!$
$F_1 = 1\,\!$
$F_k = F_{k-1} + F_{k-2}\,\!$

Assim, seus primeiros termos são: $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots\,\!$

Também é possível demonstrar que é válida a fórmula de Binet:

$F_n = \frac{\varphi ^n - \hat{\varphi}^n}{\sqrt{5}}\,\!$

onde:

$\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618\,\!$ , que é conhecido como o número de ouro;
$\hat{\varphi} = \frac{1 - \sqrt{5}}{2} = \approx -0.618\,\!$

Este livro 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 $q_0 = 1,\ldots, q_{k-1} = 1\,\!$ produzem as seguintes igualdades:

$\begin{bmatrix} a \\ b \end{bmatrix} = \overbrace{ \begin{bmatrix} \mathbf{1} & 1\\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} \mathbf{1} & 1\\ 1 & 0 \end{bmatrix}\cdot \ldots \cdot \begin{bmatrix} \mathbf{1} & 1\\ 1 & 0 \end{bmatrix} } \cdot \begin{bmatrix} d \\ 0 \end{bmatrix} = \begin{bmatrix} \mathbf{1} & 1\\ 1 & 0 \end{bmatrix}^{k+1} \cdot \begin{bmatrix} d \\ 0 \end{bmatrix}$ , sendo que $d=(a,b)\,\!$ .

Com um simples uso do princípio de indução finita, consegue-se:

$\begin{bmatrix} \mathbf{1} & 1\\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_{n}\\ F_{n} & F_{n-1} \end{bmatrix}\,\!$ , desde que $n\ge 1\,\!$ .

Deste modo,

$\begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} F_{k+2} & F_{k+1}\\ F_{k+1} & F_{k} \end{bmatrix} \cdot \begin{bmatrix} d \\ 0 \end{bmatrix} = \begin{bmatrix} d\cdot F_{k+2} \\ d\cdot F_{k+1} \end{bmatrix}$

Como $d=(a,b)\ge 1\,\!$ , segue que

$a\ge F_{k+2}\,\!$
$b\ge F_{k+1}\,\!$

Teorema

Dado $n\ge 1\,\!$ , sejam $a\,\!$ e $b\,\!$ os menores números tais que o algoritmo de Euclides aplicado a $a\,\!$ e $b\,\!$ leva exatamente $n\,\!$ passos, então $a=F_{n+2}\,\!$ e $b=F_{n+1}\,\!$ .

[editar] Exemplificando

Para determinar o valor de $(F_7, F_6) = (13, 8)\,\!$ , seria necessário efetuar cinco divisões:

$13 = 8\cdot1 + 5\,\!$

$8 = 5\cdot1 + 3\,\!$

$5 = 3\cdot1 + 2\,\!$

$3 = 2\cdot1 + \mathbf{1}\,\!$

$2 = \mathbf{1}\cdot2 + 0\,\!$

Logo, $(13,8) = 1\,\!$ . Aproveitando este exemplo, observe que:

$\begin{bmatrix} 13 \\ 8 \end{bmatrix} = \begin{bmatrix} 13 & 8\\ 8 & 5 \end{bmatrix} \cdot \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} F_{5+2} & F_{5+1}\\ F_{5+1} & F_5 \end{bmatrix} \cdot \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{5+1} \cdot \begin{bmatrix} 1 \\ 0 \end{bmatrix}\,\!$

No entanto, se qualquer dos números for menor, o algoritmo requer menos etapas. Por exemplo, ao determinar $(13, 7)\,\!$ tem-se:

$13 = 7\cdot1 + 6\,\!$

$7 = 6\cdot1 + \mathbf{1}\,\!$

$6 = \mathbf{1}\cdot6 + 0\,\!$

Donde, $(13,7) = 1\,\!$ .

Já o cálculo de $(12, 8)\,\!$ é ainda mais simples:

$12 = 8\cdot1 + \mathbf{4}\,\!$

$8 = \mathbf{4}\cdot2 + 0\,\!$

Portanto, $(12,8) = 4\,\!$ .

[editar] 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:

[editar] Teorema de Lamé

Teorema

O número de passos (de divisões) no algoritmo de Euclides com entradas $u\,\!$ e $v\,\!$ é limitado superiormente por $5\,\!$ vezes a quantidade de dígitos decimais em $min(u,v)\,\!$ .

Gabriel-Lamé

Este livro 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:

$\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618\,\!$

Tem-se:

$\varphi^2 = \varphi + 1\,\!$

Demonstração
A verificação é direta, exigindo cálculos bastante simples.

$F_n = \frac{\varphi^n}{\sqrt{5}}\,\!$ , arredondado para o inteiro mais próximo.

Demonstração
Utilizando a fórmula de Binet, basta observar que o módulo de $\hat{\varphi}\,\!$ é menor que $1\,\!$ , e consequentemente, quando $n \to \infty\,\!$ , tem-se $\hat{\varphi}^n \to 0\,\!$

$F_n \ge \varphi^{n-1}\,\!$

Demonstração

A justificativa será dada por indução:

$F_1 = 1 \ge 1 = \varphi^0\,\!$
Se for verdade que $F_n \ge \varphi^{n-1}\,\!$ , então:

$F_{n+1} = F_{n}+F_{n-1} \ge \varphi^{n-1} + \varphi^{n-2} = \varphi^{n-2}(\varphi + 1) = \varphi^{n-2}\varphi^2 = \varphi^{n}\,\!$

$\log \varphi < \frac{1}{5}\,\!$

Demonstração

De fato, valem as seguintes equivalências:

$\log \varphi < \frac{1}{5} \Leftrightarrow 5\log \varphi < 1 \Leftrightarrow \log \varphi^5 < 1 \,\!$

Mas $\varphi^5 =5\varphi + 3\,\!$ (verifique a partir de $\varphi^2 = \varphi + 1\,\!$ ), e $\varphi > \frac{8}{5} \,\!$ pois

$\varphi > \frac{8}{5} \Leftrightarrow \frac{1 + \sqrt{5}}{2} > \frac{8}{5} \Leftrightarrow 5(1 + \sqrt{5}) > 16 \Leftrightarrow 5\sqrt{5} > 11 \Leftrightarrow 125 = 25 \cdot 5 > 121\,\!$

Sendo que esta última desigualdade é verdadeira.

Como foi visto anteriormente, quando $(a,b)\,\!$ é exige exatamente $n\,\!$ passos, é tem-se $a\ge F_n+2\,\!$ e $b\ge F_n+1\,\!$ . Logo,

$a\ge F_n+2 \ge \varphi^{n+1}\,\!$

Aplicando o logaritmo em ambos os menbros, segue:

$(n+1)\log \varphi \le \log a\,\!$

ou seja

$n\le \frac{\log a}{\log \varphi} = \log_{\varphi}a\,\!$

Mas $\frac{1}{\log \varphi} < 5\,\!$ , então:

$n\le \frac{1}{\log \varphi}\cdot \log a < 5\log_{\varphi}a < 5N\,\!$ , onde $N\,\!$ é o número de dígitos de $a\,\!$

[editar] Demonstração da fórmula de Binet

Nesta seção, será deduzida a fórmula de Binet:

$F_n = \frac{1}{\sqrt{5}}\left ( \left ( \frac{1+\sqrt{5}}{2} \right )^n - \left ( \frac{1-\sqrt{5}}{2} \right )^n \right ) = \frac{\varphi ^n - \hat{\varphi}^n}{\sqrt{5}}\,\!$

onde $\varphi = \frac{1 + \sqrt{5}}{2}\,\!$ e $\hat{\varphi} = \frac{1 - \sqrt{5}}{2}\,\!$ .

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:

$\begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix}\,\!$

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

$Q = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\,\!$

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

$\begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = Q^n \cdot \begin{bmatrix} F_{1} \\ F_{0} \end{bmatrix}\,\!$

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

$\begin{bmatrix} 1 \\ 0 \end{bmatrix} = \alpha v+\alpha'v'\,\!$ , com $v\,\!$ e $v'\,\!$ sendo auto-vetores de $Q\,\!$ , ou seja, vetores não nulos tais que $Qv = \lambda_1 v\,\!$ e $Qv' = \lambda_2 v'\,\!$ , será possível obter:

$\begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = Q^n(\alpha v + \alpha' v') = \alpha (Q^n v) + \alpha' (Q^n v') = \alpha (\lambda_1^n v) + \alpha' (\lambda_2^n v')\,\!$

A partir daí será bastante simples conseguir a fórmula explicita para $F_n\,\!$ (a segunda componente do vetor à esquerda), pois $v, v', \alpha, \alpha', \lambda_1, \lambda_2\,\!$ seriam constantes.

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

$\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} x \\ y \end{bmatrix} = \lambda \begin{bmatrix} x \\ y \end{bmatrix} \Leftrightarrow \left\{\begin{matrix} x & + & y & = & \lambda x\\ x & & & = & \lambda y \end{matrix}\right.\,\!$

Logo $\lambda y + y = \lambda^2 y\,\!$ , ou seja, $(\lambda^2 -\lambda - 1)\cdot y = 0\,\!$ Assim, $y=0\,\!$ (que implica $x=0\,\!$ ) ou $\lambda^2 -\lambda - 1 = 0\,\!$ . 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:

$\lambda_1 = \varphi = \frac{1 + \sqrt{5}}{2}\,\!$
$\lambda_2 = \hat{\varphi} = \frac{1 - \sqrt{5}}{2}\,\!$

Além disso, se $\lambda\,\!$ é raiz da equação, então para cada $y\not = 0\,\!$ , o vetor

$\begin{bmatrix} \lambda y \\ y \end{bmatrix} = y \begin{bmatrix} \lambda \\ 1 \end{bmatrix}\,\!$ é um auto-vetor de $Q\,\!$ .

Em particular, se $y=1\,\!$ , os auto-vetores correspondentes a cada raiz da equação quadrática são:

$v = \begin{bmatrix} \varphi \\ 1 \end{bmatrix}\,\!$
$v'= \begin{bmatrix} \hat{\varphi} \\ 1 \end{bmatrix}\,\!$

De modo que $Qv = \varphi v\,\!$ e $Qv' = \hat{\varphi} v'\,\!$

Resta escrever $\begin{bmatrix} 1 \\ 0 \end{bmatrix} = \alpha v+\alpha'v'\,\!$ conforme se pretendia. Isso é fácil, já que são conhecidos $v = \begin{bmatrix} \varphi \\ 1 \end{bmatrix}\,\!$ e $v'= \begin{bmatrix} \hat{\varphi} \\ 1 \end{bmatrix}\,\!$ :

$\left\{\begin{matrix} 1 & = & \alpha \varphi & + & \alpha' \hat{\varphi}\\ 0 & = & \alpha & + & \alpha' \end{matrix}\right.\,\!$

Da segunda equação, segue que $\alpha' = -\alpha\,\!$ . Substituindo esse valor na primeira equação, resulta: $1 = \alpha \varphi - \alpha' \hat{\varphi} = \alpha (\varphi - \hat{\varphi})\,\!$

Como $\hat{\varphi} = 1 - \varphi\,\!$ (verifique!), tem-se $1 = \alpha (\varphi - 1 + \varphi) = \alpha (2\varphi - 1) = \alpha \sqrt{5}\,\!$ . Logo, $\alpha = \frac{1}{\sqrt{5}}\,\!$ .

Assim, $\begin{bmatrix} 1 \\ 0 \end{bmatrix} = \frac{1}{\sqrt{5}}(v - v')\,\!$ . Em consequência:

$\begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = \alpha (\lambda_1^n v) + \alpha' (\lambda_2^n v') = \frac{1}{\sqrt{5}} (\varphi^n \begin{bmatrix} \varphi \\ 1 \end{bmatrix}) - \frac{1}{\sqrt{5}} (\hat{\varphi}^n \begin{bmatrix} \hat{\varphi} \\ 1 \end{bmatrix})\,\!$

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

$F_n = \frac{1}{\sqrt{5}}(\varphi ^n - \hat{\varphi}^n)\,\!$

[editar] Exercícios

Verifique, utilizando o princípio de indução, que:

$\begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^n \cdot \begin{bmatrix} F_{1} \\ F_{0} \end{bmatrix}\,\!$
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.

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

Origem: Wikilivros, livros abertos por um mundo aberto.

Índice

[editar] Fazendo estimativas

[editar] O pior caso

[editar] Exemplificando

[editar] Melhorando as estimativas

[editar] Teorema de Lamé

[editar] Demonstração da fórmula de Binet

[editar] Exercícios

Acessos

Ferramentas pessoais

Pesquisa

Navegação

Projecto

Imprimir/exportar

Ferramentas