Alters

BigInteger - Identificación de puntos paralelos y críticos: Potenciación de BigInteger

Hola!

De nuevo por aquí, una semana más... esperando que me leáis con ganas.

Como viene siendo costumbre (creo que esta es la saga más larga que estoy haciendo), vamos a seguir con BigInteger.

En esta ocasión, toca revisar los puntos críticos de la potenciación de BigInteger.


  • ¿No es la entrada que buscabas? Entra en el índice
  • ¿Buscas el código fuente? Aquí lo tienes

¡Vamos allá!


Uno podría pensar que la fórmula de la potenciación sería muy compleja de analizar, pero, con la binarización del exponente, queda poco por analizar, ya que esencialmente cada paso de la operación depende del anterior.

No obstante, ya que cada potencia es en sí una multiplicación (y en el caso de nuestro algoritmo, pueden darse hasta 10 multiplicaciones en una operación de potenciación), tenemos la ventaja de saber que la propia multiplicación estará optimizada.

Por tanto, sin más preámbulo, el análisis de la potenciación:


Como podemos ver, la validación de "a" es lo primero que haremos; seguidamente convertimos el exponente en base binaria (algo que nos ocupará un tiempo marginal), y finalmente lanzamos las multiplicaciones encadenadas para obtener a^p .

Y con esto... por poco que parezca, hemos terminado el análisis de la potenciación.

En la próxima entrada, veremos la operación de raíz, y os prometo que habrá más contenido :-)


Hasta la próxima!

No hay comentarios:

Publicar un comentario