Determine o número de multiplicações usadas para encontrar x^{2 k} começando \operatorname{com} x e elevando ao quadrado sucessivamente (para encontrar x^{2}, x^{4}, e assim por diante). Esta é a maneira mais eficiente de encontrar x^{2 k} em vez de multiplicar x por ele mesmo quantas vezes forem necessárias?

Passo 1

O enunciado pede para calcular \,x^{2^k} (note que cada “elevar ao quadrado” dobra o expoente: x\to x^2\to x^4\to x^8 e assim por diante) usando exclusivamente sucessivas operações de quadrado. O conteúdo é a técnica de potenciação por quadrados sucessivos, e queremos contar quantas multiplicações ela usa.

Passo 2

Cada vez que elevamos um valor y ao quadrado, fazemos uma multiplicação:
– Para obter x^2, usamos 1 multiplicação.
– Para obter x^4=(x^2)^2, usamos mais 1 multiplicação.
– Em geral, para passar de x^{2^{i-1}} a x^{2^{i}} precisamos de exatamente 1 multiplicação.

Passo 3

Como começamos em x^{2^0}=x e queremos chegar a x^{2^k}, damos k quadrados sucessivos. Logo, o número total de multiplicações é k.

Passo 4

Compare com o método ingênuo de multiplicar x por si mesmo repetidamente até obter x^{2^k}: seriam 2^k-1 multiplicações. Para k razoavelmente grande, k\ll2^k-1, então o ganho é exponencial.

Passo 5

Para ver que não dá para usar menos de k multiplicações, note que cada multiplicação só pode no máximo somar os expoentes dos dois fatores. Partindo de expoente 1, após m multiplicações o maior expoente que se consegue é 2^m. Se quisermos 2^m\ge2^k, precisa m\ge k. Portanto, k multiplicações é o mínimo possível.

Resposta

O número de multiplicações é k, e esse procedimento de quadrados sucessivos é, de fato, o mais eficiente para obter x^{2^k} no modelo que só permite multiplicações.

Exercícios de Livros Relacionados