Hola de nuevo!
En esta entrada, vamos a seguir ahondando en la arquitectura de BigInteger.
En este caso, vamos a entrar en la operación de raíz de BigInteger.
¡Vamos allá!
Para esta operación, no quise limitar la imaginación... y en lugar de hacer la típica raíz cuadrada, se da la opción de hacer la n-ésima raíz de un BigInteger.
Como habréis intuido, esta función también tendrá como entrada un BigInteger y un dato int, que indicará el índice de la raíz.
De nuevo, esta operación ha sido optimizada para obtener un buen rendimiento.
La función empieza como el resto, valida los datos y los copia en una variable temporal.
Acto seguido, se calcula "BigInteger.count / 2", para obtener una potencia base.
Esto se debe a que al aplicar la raíz cuadrada (el tipo de raíz más bajo) el resultado siempre tiene como mínimo la mitad de la longitud.
A este dato lo llamaremos "base", y será un valor fijo.
Además, crearemos un nuevo valor "raw", que tendrá el valor inicial de "base" e irá pivotando para encontrar un valor adecuado.
Para obtener el resultado, aplicaremos un teorema que siempre me ha gustado: El Teorema de Bolzano.
Básicamente, este Teorema nos dice que dada una función lineal y continua en un rango, si dicha función pasa por dos puntos, pasa por todos los puntos intermedios.
Os quedáis igual, ¿verdad? Un ejemplo práctico: si subes en un ascensor en el tercer piso, y bajas hasta el bajo (y asumiendo que no bajas del ascensor en ningún momento, y que el trayecto es directo sin paradas), es imposible que no pases por el segundo piso.
Y eso es un hecho; no hay vuelta de hoja.
¿Y cómo aplicas este Teorema a la raíz cuadrada? Aquí está lo bueno.
- Calculas ret = base^n, donde "n" es el índice de la potencia
- Entras en un bucle que se repite hasta que base = 0, o bien se encuentre un resultado exacto
- Mientras ret < a (donde "a" es el valor del que queremos la potencia)
- Calculas "raw = raw + base" (vamos incrementado la cifra actual)
- Calculas "ret = raw^n
- Al salir del bucle, siempre se dará "a >= ret", ya que hemos forzado la situación
- Si "a > ret"
- Calculas "raw = raw - base" (te has pasado, vamos al anterior)
- Calculas "base = base / 10" (bajas una cifra el valor de base)
- Si "base" tiene un valor de 0, has llegado al resultado
- Si no, decimos que "ret < a" (ya que hemos restado "base"). Con esto, se ajustará el siguiente dígito del resultado
Finalmente, se copia "ret" a la salida, y se limpia la memoria.
En definitiva, el cálculo de la raíz se hace a base de buscar "excesos" en resultados parciales, y yendo disminuyendo la precisión del dato que se va sumando, de manera que finalmente se alcanza el valor final.
Y con esto, llegamos al final de las operaciones complejas.
En la próxima entrada veremos todas las funciones auxiliares (ocupar una entrada por función sería excesivo, ya que son funciones pequeñas).
¡Nos vemos!
No hay comentarios:
Publicar un comentario