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

 

o menor índice inteiro <math>t\,\!</math> que torna <math>\frac{a}{2^t}\,\!</math> menor que <math>1\,\!</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:

 

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

:<math>\log_2 a < N\cdot\log_2 10\,\!</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>.