Algoritmo de exponenciación rápida - ¿Cómo llegar a él?

Question

He estado aprendiendo sobre la exponenciación rápida cuando encontré este algoritmo:

int expo(int a, int b) {
  int result = 1;

  while (b) {
    if (b%2==1) {
      result *= a;
    }
    b /= 2;
    a *= a;
  }

  return result;
}

Se supone que esto calcula $a^b$ en tiempo logarítmico, pero no pude entender ni encontrar en ningún lugar cómo llegar a este procedimiento, aparte de notar que (esta fórmula en particular no me ayudó a entender por qué el algoritmo es correcto):

$$ x^n = \begin{cases} 1 & \text{si $n=0$} \\ \frac{1}{x}^{-n} & \text{si $n<0$} \\ x \cdot \left( x^{\frac{n-1}{2}} \right)^2 & \text{si $n$ es impar} \\ \left( x^{\frac{n}{2}} \right)^2 & \text{si $n$ es par} \end{cases} $$

Por lo que entiendo, la transición de esta identidad particular al algoritmo real es bastante obvia, pero sinceramente no lo entiendo y he trabajado manualmente en bastantes ejemplos para este algoritmo.

¿Alguien puede explicar?

Answer 1

Escribe $b = b_0 + b_1 2 + b_2 2^2 + ... + b_n 2^n$ donde $b_k$ son los dígitos binarios de la representación de $b$ en base $2$. Ten en cuenta que $n$ varía de forma logarítmica con $b$. Entonces:

$$ a^b = a^{b_0} \cdot (a^2)^{b_1} \cdot (a^{2^2})^{b_2} \cdot ... \cdot (a^{2^n})^{b_n} $$

Los términos donde los bits $b_k = 0$ se evalúan como $1$ y pueden omitirse. Los términos con $b_k = 1$ son de la forma $a^{2^k}$ y se pueden calcular mediante el cuadrado repetido de $a$ $k$ veces. Esto es precisamente lo que hace el código publicado.

Answer 2

El algoritmo utiliza la expansión binaria del exponente para reducir la cantidad de multiplicaciones que uno tiene que hacer. Si tomas $a$ y lo elevas al cuadrado y luego lo vuelves a elevar al cuadrado y luego al cuadrado de nuevo, produces los números $a, a^2, a^4, a^8,\ldots,a^{2^k}$ hasta que $2^{k+1}>b$ es Entonces eso toma alrededor de $\log_2 b$ multiplicaciones. Luego, si expresas $b$ en binario, digamos, $b=1101001$, entonces $a^b = a^{2^6+2^5+2^3+2^0} = a^{2^6}a^{2^5}a^{2^3}a^{2^0}$, y acabas de calcular todos estos poderes de $a$, así que multiplícalos juntos y eso son alrededor de $\log_2 b$ multiplicaciones más.

Answer 3

Apenas entiendo tu código, pero aquí está la descripción del algoritmo en pseudo-código: consideramos los valores sucesivos de los cuadrados, denotados por $S$, y por $P$ los valores sucesivos de las potencias del número $a:

Entrada: $\;a, n$

Salida: $\;a^n$

$S\leftarrow a$, $P\leftarrow a$ ;

Mientras $n>1$ hacer

$\qquad$Si impar($n$) $\;P\leftarrow P*S\enspace$ fin \begin{align*} &n\leftarrow \Bigl\lfloor n/2\Bigr\rfloor&\hspace25em\\ &S\leftarrow S^2 \end{align*}

FinMientras

$P\leftarrow P*S$.

Fin

Answer 4

Si deseas hacer algo en tiempo logarítmico, probablemente necesites hacer algo con los dígitos del número en alguna base, en lugar de con el número en sí. La representación digital de un número es inherentemente un objeto logarítmico. Además, dado que $b$ es lo que determina principalmente cuán grande es $a^b$, probablemente necesitaremos pensar en $b$ de forma logarítmica, o de lo contrario no tendremos esperanzas de hacer que nuestro algoritmo sea logarítmico.

Si ahora consideras $b$ en base $2$, este es el algoritmo natural que resulta.

También se puede estar inspirado en el algoritmo de búsqueda binaria, que consiste en encontrar un elemento en una lista ordenada. Funciona dividiendo la lista en dos, determinando si el elemento está en la primera (respectivamente segunda) mitad de la lista, y repitiendo el algoritmo usando la lista ahora de la mitad de tamaño que es la primera (respectivamente segunda) mitad de la original. Esta idea de "dividir y conquistar" aparece por todas partes si queremos hacer cosas en tiempo logarítmico; el algoritmo que has dado es una respuesta natural a la pregunta "¿podemos dividir y conquistar esto?".

Answer 5

Intenta exponenciar solo sumando exponentes, hazlo en la menor cantidad de pasos posible. Luego piensa en cómo obtener un exponente real para realizar la multiplicación. La forma en que se hace en el algoritmo asegura que puedes reciclar cada variable en el algoritmo.

Vamos a definir nuestra función

slowExpo(x,y)

pasos:

1. Genera una secuencia de sumas que sumen y. $y_i$
2. Genera una secuencia de $x^{y_i}$.
3. Multiplica cada miembro de la secuencia del paso 2.
4. Devuelve la salida del paso 3, es x^y.

Esto funciona debido a las leyes de adición de exponentes.

$a^b * a^c = a^{b+c}$

La secuencia generada en tu algoritmo está diseñada para binario y para reciclar cada miembro de la secuencia generada, y realiza los pasos 1, 2 y 3 juntos "en pseudo-paralelo" en un solo bucle, esto reduce la cantidad de trabajo, porque las listas reales de secuencias no tienen que ser almacenadas/recuperadas y la versión exponenciada de $x^{y_i}$, no tiene que ser calculada mediante la recursividad como slowExpo(x,y_i).