Determine o número de multiplicações usadas para encontrar
começando
e elevando ao quadrado sucessivamente (para encontrar
, e assim por diante). Esta é a maneira mais eficiente de encontrar
em vez de multiplicar
por ele mesmo quantas vezes forem necessárias?
Passo 1
O enunciado pede para calcular
(note que cada “elevar ao quadrado” dobra o expoente:
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
ao quadrado, fazemos uma multiplicação:
– Para obter , usamos 1 multiplicação.
– Para obter , usamos mais 1 multiplicação.
– Em geral, para passar de a
precisamos de exatamente 1 multiplicação.
– Para obter
– Para obter
– Em geral, para passar de
Passo 3
Como começamos em
e queremos chegar a
, damos
quadrados sucessivos. Logo, o número total de multiplicações é
Passo 4
Compare com o método ingênuo de multiplicar
por si mesmo repetidamente até obter
: seriam
multiplicações. Para
razoavelmente grande,
, então o ganho é exponencial.
Passo 5
Para ver que não dá para usar menos de
multiplicações, note que cada multiplicação só pode no máximo somar os expoentes dos dois fatores. Partindo de expoente
, após
multiplicações o maior expoente que se consegue é
. Se quisermos
, precisa
. Portanto,
multiplicações é o mínimo possível.
Resposta
O número de multiplicações é
, e esse procedimento de quadrados sucessivos é, de fato, o mais eficiente para obter
no modelo que só permite multiplicações.