Teoria de números/Eficiência do algoritmo de Euclides: diferenças entre revisões
| [edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
m organizando |
m + img. +cm |
||
Linha 76:
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>.
===
<!-- Foi mostrado que a sequência dos restos decresce geometricamente, ou seja, além de ser verdade que
:<math>a \ge b > r_0 > r_1 > \ldots > r_k > r_{k+1} = 0\,\!</math>
Linha 133:
* <math>b\ge F_{k+1}\,\!</math>
=== Teorema de Lamé ===▼
{{Teorema|texto=
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>.
Linha 174 ⟶ 173:
|}
Portanto, <math>(12,8) = 4\,\!</math>.
== 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|texto=
O número de passos de divisão 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>.
}}
{| width="100%" style="border:1px solid #6688AA;-moz-border-radius:1em; background-color:#F0F9FF; padding:1em; width:120px<!--50%-->; float:right; clear:right; " valign="top"|
|-
|<big><big>Gabriel-Lamé</big></big>
[[Image:Gabriel-Lamé.jpeg|100px|center]]<!--|right-->
|}
== Exercícios ==
| |||