Square-And-Multiply

Damián Jueves 18 de Enero del 2007

Seguramente a estas alturas ya les habrán pedido que programen la exponenciación entera de un número para ilustrarles algunas estructuras de control, pero es muy probable que no se hayan preguntado cómo se podría hacer más eficiente una exponenciación o de plano pensaron que es lo mejor que se puede hacer (hacer todas y cada una de las multiplicaciones).

Aqui les voy a exponer un método sencillo y muy usado para exponenciar en grande de una manera más eficiente.

El Algoritmo para exponenciación se llama Square-And-Multiply(SQM), se basa en el principio de cambiar el exponente a una base más pequeña (base dos) para asi lograr un número menor de multiplicaciones. Este resultado no sería posible sin algunos resultados sobre exponentes y logaritmos.

Imaginemos que queremos calcular $3^{14}$ , si no conocemos mas que la definición de potencia entonces nos veríamos en el caso de multiplicar $14$ veces $3$ para así llegar al resultado, pero ahora pensemos en cómo podríamos escribir $14$ en base $2$ (binario). Tendríamos que $14_{10}=1110_2$ y en sistema decimal tendríamos que $14=1 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0$ .

Asi que viendo lo anterior pues ahora se nos podría ocurrir escribir:
$3^{14}=3^{1 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0}=\left(3^2}\right)^3 \cdot \left(3^2\right)^2 \cdot 3^2$

Que listillos, ¿no? Seguramente ya se habrán dado cuenta de lo que se tiene que hacer. Primero que nada no contar los lugares donde haya un $0$ como digito significativo en el exponente porque sabemos que es un $1$ a la hora de multiplicar. El algoritmo completo quería así:

PotenciaSQM (b,n)
   binexp  PasaABinario(n)
   p  1
   s  b
   if n > 0 then
      if binexp[0] = 1 then
          p  b
      endif
      for  do
           
           if binexp[j] = 1 then
              p  p*s
           endif
      endfor
   endif
   return p
end

¿En qué es mejor este algoritmo?

Si piensan con más detenimiento se darán cuenta de que se tienen que hacer a lo más $2 \cdot\log_2(n)$ multiplicaciones (sin contar el cambio de base del exponente), y esa función se va “achaparrando” mucho en comparación con $g(n)=n$ que serían el número de multiplicaciones que se tendrían que hacer si se hiciera la exponenciación “a pie”. Por ello es un buen método para exponenciar con números muy grandes, ya que entre más grande sea el exponente se verá más la eficiencia de este método.