Teoria de números/Máximo divisor comum: diferenças entre revisões
| [edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
m ajustes, links e correções |
|||
Linha 345:
== Número de passos ==
Nesta seção, será discutido quão eficiente é o algoritmo de Euclides para o cálculo do MDC.
''Quantas etapas (divisões) do algoritmo são necessárias para que o resto <math>r_{k+1}\,\!</math> seja zero?''
Recorde-se que o algoritmo baseia-se na construção da sequência:
:<math>a \ge b > r_0 > r_1 > \ldots > r_k > r_{k+1} = 0\,\!</math>
cujos termos verificam as seguintes igualdades:
Linha 384 ⟶ 388:
:<math>r_{2j+1}<a/2^{j+1}\,\!</math>
Com isso, a sequência dos <math>r_j\,\!</math> decresce [[w:Progressão geométrica#Progressão geométrica decrescente|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 um. 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^j}\,\!</math> menor que um é
:<math>t = [ \log_2 a ] + 1\,\!</math>
Onde <math>[ \alpha ]\,\!</math> denota o maior inteiro que não supera <math>\alpha\,\!</math> (a ''parte inteira de <math>\alpha\,\!</math>'').
Mas <math>r_{2t} < \frac{a}{2^{t+1}} < 1\,\!</math> implica que <math>r_{2t} = 0</math>, pois os restos são números inteiros.
Assim, se o algoritmo para quando <math>r_{k+1} = 0\,\!</math>, certamente <math>k+1\,\!</math> não pode ser maior que o índice <math>2t\,\!</math>, ou seja:
:<math>k+1 \le [ \log_2 a ] + 1\,\!</math>
Para melhor compreender o significado dessa estimativa, considere que <math>a\,\!</math> tem <math>N\,\!</math> dígitos. Então:
:<math>a < 10^N\,\!</math>
Aplicando o logaritmo em ambos os membros, resulta
:<math>\log_2 a < N\cdot\log_2 10\,\!</math>
Logo, <math>k+1 \le 2[\log_2 a] +1< 2(N\cdot\log_2 10 + 1) \approx 6,6N\,\!</math>
Embora muito útil, esta ainda não é a melhor aproximação que pode ser obtida algebricamente.
=== Fórmula de Binet ===
| |||