Teoria de números/Eficiência do algoritmo de Euclides: diferenças entre revisões

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

|align=center width=50px|'''1''' ||align=right| <math>r_0 =\,\!</math> || width=200px | <math>r_1q_0+r_2\,\!</math> || <math>0 \le r_2<r_1\,\!</math>

|align=center|'''2''' ||align=right| <math>r_1 =\,\!</math> || <math>r_2q_1+r_3\,\!</math> || <math>0 \le r_3<r_2\,\!</math>

| ||align=right| <math>\vdots\,\!</math> || ||

|align=center|'''k-1''' ||align=right| <math>r_{k-2} =\,\!</math> || <math>r_{k-1}q_{k-2}+r_{k}\,\!</math> || <math>0 \le r_{k}<r_{k-1}\,\!</math>

|align=center|'''k''' ||align=right| <math>r_{k-1} =\,\!</math> || <math>r_{k}q_{k-1}+r_{k+1} = r_{k}q_{k-1}\,\!</math> || pois <math>0 = r_{k+1}<r_{k}\,\!</math>

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

:<math>r_0 = r_1q_0+r_2 \ge r_1+r_2 > 2r_2\,\!</math>

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

:<math>r_0 > 2r_2\,\!</math>

:<math>r_1 > 2r_3\,\!</math>

:<math>r_2 > 2r_4\,\!</math>

:<math>r_3 > 2r_5\,\!</math>

:<math>r_{k}>2r_{k+2}\,\!</math>, para cada <math>k\ge 0\,\!</math>.

:<math>r_{0}<a/2\,\!</math>

:<math>r_{2}<r_{0}/2<a/4\,\!</math>

:<math>r_{4}<r_{2}/2<r_{0}/4<a/8\,\!</math>

:<math>\ldots\,\!</math>

:<math>r_{2j}<a/2^{j+1}\,\!</math>

:<math>r_{2j+1}<a/2^{j+1}\,\!</math>

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

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

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

:<math>\frac{a}{2^{x}} < 1 \Leftrightarrow a < 2^{x} \Leftrightarrow \log_2 a < x \,\!</math>

o menor índice inteiro <math>t\,\!</math> que torna <math>\frac{a}{2^t}\,\!</math> menor que <math>1\,\!</math> é

:<math>t = \lfloor \log_2 a \rfloor + 1\,\!</math>

Onde <math>\lfloor \alpha \rfloor\,\!</math> denota o maior inteiro que não supera <math>\alpha\,\!</math> (a [[w:Parte inteira|parte inteira]] de <math>\alpha\,\!</math>).

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

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

:<math>k+1 \le 2(\lfloor \log_2 a \rfloor + 1)\,\!</math>

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

:<math>10^{N-1}\le a < 10^N\,\!</math>

:<math>\log_2 a < N\cdot\log_2 10\,\!</math>

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

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

:<math>a \ge b > r_0 > r_1 > \ldots > r_k > r_{k+1} = 0\,\!</math>

* <math>r_{2j }<a/2^{j+1}\,\!</math>

* <math>r_{2j+1}<a/2^{j+1}\,\!</math>

:''Qual é o menor valor de <math>a\,\!</math> para o qual o algoritmo leva <math>n\,\!</math> passos?''

Para <math>n=1\,\!</math>:

:<math>\begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} q_0 & 1\\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} d \\ 0 \end{bmatrix}\,\!</math>

Para <math>n=2\,\!</math>:

:<math>\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}\,\!</math>

Para <math>n=3\,\!</math>:

:<math>\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}\,\!</math>

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

Se cada quociente for substituído por <math>1\,\!</math> na fórmula de recorrência

:<math>r_{j-1} = r_jq_{j-1} + r_{j+1}\,\!</math>

:<math>r_{j-1} = r_j + r_{j+1}\,\!</math>

Que vale para <math>j\,\!</math> satisfazendo <math>1\le j\le k\,\!</math>.

* <math>F_0 = 0\,\!</math>

* <math>F_1 = 1\,\!</math>

* <math>F_k = F_{k-1} + F_{k-2}\,\!</math>

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

:<math>F_n = \frac{\varphi ^n - \hat{\varphi}^n}{\sqrt{5}}\,\!</math>

* <math>\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618\,\!</math>, que é conhecido como o [[w:número de ouro|número de ouro]];

* <math>\hat{\varphi} = \frac{1 - \sqrt{5}}{2} = \approx -0.618\,\!</math>

Matricialmente, as condições <math>q_0 = 1,\ldots, q_{k-1} = 1\,\!</math> produzem as seguintes igualdades:

:<math>\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}</math>, sendo que <math>d=(a,b)\,\!</math>.

:<math>\begin{bmatrix} \mathbf{1} & 1\\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_{n}\\ F_{n} & F_{n-1} \end{bmatrix}\,\!</math>, desde que <math>n\ge 1\,\!</math>.

Como <math>d=(a,b)\ge 1\,\!</math>, segue que

* <math>a\ge F_{k+2}\,\!</math>

* <math>b\ge F_{k+1}\,\!</math>

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

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

|align=right| <math>13 = 8\cdot1 + 5\,\!</math>

|align=right| <math>8 = 5\cdot1 + 3\,\!</math>

|align=right| <math>5 = 3\cdot1 + 2\,\!</math>

|align=right| <math>3 = 2\cdot1 + \mathbf{1}\,\!</math>

|align=right| <math>2 = \mathbf{1}\cdot2 + 0\,\!</math>

Logo, <math>(13,8) = 1\,\!</math>. Aproveitando este exemplo, observe que:

:<math>\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}\,\!</math>

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

|align=right| <math>13 = 7\cdot1 + 6\,\!</math>

|align=right| <math>7 = 6\cdot1 + \mathbf{1}\,\!</math>

|align=right| <math>6 = \mathbf{1}\cdot6 + 0\,\!</math>

Donde, <math>(13,7) = 1\,\!</math>.

Já o cálculo de <math>(12, 8)\,\!</math> é ainda mais simples:

|align=right| <math>12 = 8\cdot1 + \mathbf{4}\,\!</math>

|align=right| <math>8 = \mathbf{4}\cdot2 + 0\,\!</math>

Portanto, <math>(12,8) = 4\,\!</math>.

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

:<math>\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618\,\!</math>

* <math>\varphi^2 = \varphi + 1\,\!</math>

* <math>F_n = \frac{\varphi^n}{\sqrt{5}}\,\!</math>, arredondado para o inteiro mais próximo.

|Utilizando a fórmula de Binet, basta observar que o módulo de <math>\hat{\varphi}\,\!</math> é menor que <math>1\,\!</math>, e consequentemente, quando <math>n \to \infty\,\!</math>, tem-se <math>\hat{\varphi}^n \to 0\,\!</math>

* <math>F_n \ge \varphi^{n-1}\,\!</math>

# <math>F_1 = 1 \ge 1 = \varphi^0\,\!</math>

# Se for verdade que <math>F_n \ge \varphi^{n-1}\,\!</math>, então:

:<math>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}\,\!</math>

* <math>\log \varphi < \frac{1}{5}\,\!</math>

<math>\log \varphi < \frac{1}{5} \Leftrightarrow 5\log \varphi < 1 \Leftrightarrow \log \varphi^5 < 1 \,\!</math>

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

:<math>\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\,\!</math>

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

:<math>a\ge F_n+2 \ge \varphi^{n+1}\,\!</math>

:<math>(n+1)\log \varphi \le \log a\,\!</math>

:<math>n\le \frac{\log a}{\log \varphi} = \log_{\varphi}a\,\!</math>

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

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

:<math>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}}\,\!</math>

onde <math>\varphi = \frac{1 + \sqrt{5}}{2}\,\!</math> e <math>\hat{\varphi} = \frac{1 - \sqrt{5}}{2}\,\!</math>.

:<math>\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}\,\!</math>

:<math>Q = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\,\!</math>

:<math>\begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = Q^n \cdot \begin{bmatrix} F_{1} \\ F_{0} \end{bmatrix}\,\!</math>

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

:<math>\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')\,\!</math>

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

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

\end{matrix}\right.\,\!</math>

Logo <math>\lambda y + y = \lambda^2 y\,\!</math>, ou seja, <math>(\lambda^2 -\lambda - 1)\cdot y = 0\,\!</math>

Assim, <math>y=0\,\!</math> (que implica <math>x=0\,\!</math>) ou <math>\lambda^2 -\lambda - 1 = 0\,\!</math>. O primeiro caso não é de interesse, pois auto-vetores não são nulos.

* <math>\lambda_1 = \varphi = \frac{1 + \sqrt{5}}{2}\,\!</math>

* <math>\lambda_2 = \hat{\varphi} = \frac{1 - \sqrt{5}}{2}\,\!</math>

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

:<math>\begin{bmatrix} \lambda y \\ y \end{bmatrix} = y \begin{bmatrix} \lambda \\ 1 \end{bmatrix}\,\!</math> é um auto-vetor de <math>Q\,\!</math>.

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

* <math>v = \begin{bmatrix} \varphi \\ 1 \end{bmatrix}\,\!</math>

* <math>v'= \begin{bmatrix} \hat{\varphi} \\ 1 \end{bmatrix}\,\!</math>

De modo que <math>Qv = \varphi v\,\!</math> e <math>Qv' = \hat{\varphi} v'\,\!</math>

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

\end{matrix}\right.\,\!</math>

Da segunda equação, segue que <math>\alpha' = -\alpha\,\!</math>. Substituindo esse valor na primeira equação, resulta:

<math>1 = \alpha \varphi - \alpha' \hat{\varphi} = \alpha (\varphi - \hat{\varphi})\,\!</math>

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

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

:<math>\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})\,\!</math>

:<math>F_n = \frac{1}{\sqrt{5}}(\varphi ^n - \hat{\varphi}^n)\,\!</math>

#:<math>\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}\,\!</math>