La potencia de las potencias

Buenas!

Vaya, este año parece que estoy algo más presente por el blog, y yo que me alegro... resulta que estoy haciendo algunos avances en una librería que cree para mi TFG, y hoy os voy a compartir una cosilla un tanto curiosa que seguro os gustará

¡Vamos allá!



Para empezar, comentar que la librería está escrita en C, al 100%, y sin ningún tipo de framework... ya sabéis... ¡el escepticismo!

La librería está pensada para trabajar con números grandes... muy similar a "BigInteger" de Java; de hecho, la librería se llama "BigInteger.c" y la podéis encontrar en mi perfil de GitHub.

Básicamente se compone de las operaciones básicas (suma, resta, multiplicación y división), además de dos operaciones complejas: la raíz cuadrada y la potenciación.

Y de esta última os voy a comentar...

Uno diría que realizar una potencia "a^b", bastaría con multiplicar "a" por si mismo "b" veces - y de hecho, así es; pero cuando trabajamos con números de grandes cifras, la cosa se complica, ya que queremos que trabaje de manera óptima, y la manera que hemos descrito no lo es.

Supongamos que queremos calcular "a^151", y digamos que "a" tiene unas diez cifras.
Tras hacer "a * a", el resultado tendría 18 cifras aproximadamente, es decir "(longitud(a) - 1) * 2)". Como veis, a poco que crezca el número, el cálculo se vuelve más y más pesado... por tanto, cuanto menos pasos tengamos que hacer, mejor ¿verdad?

Y... ¿cómo nos saltamos algunos pasos? Pues, aplicando las propiedades de las potencias (aunque seguramente, como yo, no las tenéis frescas ¡yo os refresco, no problem!

Vamos a explotar una de las propiedades más básicas de las potencias: Dadas dos potencias con la misma base, que se multiplican, el resultado se puede expresar como una potencia única cuyo exponente es la suma de los exponentes de los factores.

Es decir...

(a^b) * (a^c) = (a^(b + c))

Con esto, nos ahorraremos bastantes operaciones, aprovechando algunos trucos... para empezar, nos tenemos que quedar con la siguiente idea:

a * a = a^2
a^2 * a^2 = a^4
a^4 * a^4 = a^8
...

¿Veis por donde van los tiros? estamos consiguiendo potencias de "a" con formato "a^2^n", es decir: 1, 2, 4, 8, 16, 32, 64, ...

A la vez, los valores tipo 2^n son calculables de una manera sencilla... básicamente, si convertimos un número decimal en binario tendríamos la solución.

binario(151) = 10010111

Es decir

151 = 2^7 + 2^4 + 2^2 + 2^1 + 2^0;
151 = 128 + 16 + 4 + 2 +1;
151 = 128 + 20 + 3;
151 = 148 + 3

Por tanto, solo tenemos que calcular

a^2^0
a^2^1
a^2^2
a^2^4
a^2^7

Y luego multiplicar todos estos valores entre si.

Finalmente, para entrar un poco en código (aunque simplificado), una interpretación de esta función en JavaScript sería la siguiente:

[code lan=gral] pow(8, 151); function dectobin(t){ let x = 0; let z = ""; while(t > 0){ x = Math.floor(t / 2); z += (t - x * 2); t = x; } console.log(z); return z; } function pow(a, b){ let x = dectobin(b); let t = 1; let i = 0; let m = 0; let z = 1; let r = 1; for(;i<x.length;i++){ console.log("Potencia: 2^" + i + " = " + t); if(i == 0){ z = a; }else{ z = z * z; } if(x.charAt(i) == "1"){ m = m + t; console.log("Contar"); r = r * z; } t = 2 * t; console.log("z: " + z); console.log("---------"); } console.log("Resultado Final: " + r); [/code]

Aunque el código es un poco confuso al principio, básicamente hacemos lo siguiente:

• Obtenemos la representación binaria del exponente
• Vamos obteniendo los diferentes valores de "2^n"
• Si corresponde añadir el valor, lo multiplicamos

Con esto, nos vemos obligados a calcular desde 2^0 hasta 2^n (en nuestro caso, 2^7), pero aún así, haríamos un total de 12 operaciones, frente las 151 que deberíamos hacer de manera "normal".

Pues nada... esta es la potencia de las potencias! Espero que os haya entretenido, al menos...

¡Nos vemos!