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 división de BigInteger.
¡Vamos allá!
La división, ya os adelanto, es la más caótica de las operaciones. En el desarrollo de la arquitectura reescribí la función tres veces en tres semanas, ya que me resultó bastante complicado llegar a una solución óptima y funcional.
Por eso, en cuanto a organización de código, es algo más desordenada, aunque a nivel funcional es bastante entendible.
El desarrollo de la función empieza como todas: validando los datos.
Una vez validados los datos, se copian los operandos "a" y "b" a variables temporales, y se extrae el signum.
Acto seguido se normaliza siguiendo la norma de signum siguiente:
- Signum 0: No se realiza ninguna acción.
- Signum 1: Se cambia el signo de "b".
- Signum 10: Se cambia el signo de "a".
- Signum 11: Se cambia el signo de "a" y de "b".
Como sucede en la multiplicación, se hacen unas validaciones para mejorar el rendimiento.
- Si "a = b", se devuelve el valor "1".
- Si "a < b", se devuelve el valor "0".
- Si "a > b", y "b > 1", se realiza la división (en caso contrario se devuelve "a").
Antes de seguir, y como anécdota, comentar que, debido a esta optimización, existe un curioso bug (si lo queréis llamar así) por el que "0/0 = 1". Ya que este caso será improbable, se decidió dejar así, ya que es, cuanto menos, curioso.
Siguiendo con el algoritmo de la función... una vez realizadas las operaciones, si los signos son diferentes (signum "1" o "10"), se cambia el signo, y finalmente se copian los datos a la salida y se libera la memoria.
Ahora nos queda ahondar en la división en si. Esta parte del algoritmo se apoya, de nuevo, en BIT (que como ya vimos en la multiplicación de BigInteger, es un buffer intermedio).
Los datos iniciales de BIT son
- BIT[0] = 0
- BIT[1] = b
Una vez tenemos BIT inicializado, nos quedamos con "b.count" dígitos, a excepcion de si "b" tienen un único dígito, en cuyo caso no hacemos nada; con los posibles "b.count" dígitos los almacenamos en un BigInteger temporal.
Esta parte, correspondería prácticamente al algoritmo "tradicional" de reservar tantas cifras del numerador como cifras tenga el denominador.
Ahora, por cada cifra de diferencia entre "a" y "b", guardamos la n-ésima cifra de "a", y la añadimos al dato temporal (esto es, "bajamos" la siguiente cifra).
El número resultante se compara con los candidatos existentes en BIT, de la siguiente manera:
- Se compara el número resultante (temp) con el último número usado de BIT (max).
- Si "temp > max", vamos generando nuevos valores consecutivos de BIT hasta que "temp <= max".
- Si "temp = max", no hacemos nada, ya tenemos el valor
- Si "temp < max", vamos retrocediendo en BIT hasta encontrar un BIT tal que "temp >= max", y entonces recuperamos el valor posterior (que será el primero que cumpla "temp <= max".
- Añadimos el índice de BIT al resultado (es decir, el índice de BIT es el resultado de temp / max)
- Restamos "temp = temp - max"
Finalmente, recontamos los dígitos (pues posiblemente el número resultante tenga menos dígitos), y habríamos terminado.
Por último, como siempre, dejo el flujo en formato visual para vuestro deleite.
Con esto, queda terminada la sección de funciones básicas.
Nos queda profundizar en las operaciones complejas, en las utilidades, y habremos completado la documentación del estado actual de BigInteger!
Espero que os haya agradado la entrada, y como siempre, hasta la próxima.
¡Nos vemos!
No hay comentarios:
Publicar un comentario