Comparando el número de multiplicaciones para calcular $a^{2^n}$

Question

Compare el número de multiplicaciones utilizadas por ambos algoritmos a continuación para evaluar $a^{2^n}$,

Y el segundo algoritmo para evaluar $a^{2^n}$,

El primer algoritmo producirá $2^n$ multiplicaciones mientras que el segundo producirá solo $n$ multiplicaciones.

Pregunta 1: Estoy tratando de entender por qué el primer algoritmo hace $2^n$ multiplicaciones mientras que el segundo hace $n$ multiplicaciones. En mi intento por averiguar el número de multiplicaciones, encuentro que el primer algoritmo hace las siguientes multiplicaciones,

$$n = 1\longrightarrow (a\cdot 1),1 ~~ multiplicación$$ $$n = 2\longrightarrow a\cdot (a\cdot 1), 2 ~~ multiplicaciones$$ $$\cdots$$ $$n = k\longrightarrow a\cdots(a\cdot 1),~~ k ~~ multiplicaciones$$

Entonces, ¿cómo hace el primer algoritmo las $2^n$?

Pregunta 2: De manera similar, para el segundo algoritmo, $$n = 1\longrightarrow (a\cdot a),1 ~~ multiplicación$$ $$n = 2\longrightarrow (a\cdot a)^2=(a\cdot a)(a\cdot a), 3 ~~ multiplicaciones$$ $$n = 3\longrightarrow ((a\cdot a)(a\cdot a))^2=(a\cdot a)(a\cdot a)(a\cdot a)(a\cdot a),~~ 7 ~~ multiplicaciones$$ $$\cdots$$

Entonces, no estoy seguro por qué el segundo algoritmo solo hace $n$ multiplicaciones?

Answer 1

El primer algoritmo es esencialmente $$\underbrace{a \cdot \ldots \cdot a}_{2^n \text{ veces}},$$ así que haces $2^n$ multiplicaciones (multiplicando con $a$ cada vez). El segundo algoritmo hace $$(\ldots((a\overbrace{^2)^2)\ldots)^2}^{n \text{ veces}},$$ así que estás multiplicando el resultado consigo mismo $n$ veces (no con $a$). Esa es la diferencia.