Buenas!
Vamos a seguir con la documentación de la arquitectura BigInteger.
En esta ocasión, vamos a explicar la suma de dos BigInteger.
El funcionamiento básico de la suma se basa en operaciones parciales dígito a dígito (en realidad, todas las operaciones están planteadas como conjuntos de operaciones parciales); pero no todo es tan sencillo como parece - hay que tener en cuenta algunos factores.
Pasando a la explicación, comentar que, como ya anticipamos, la función de suma trabaja a partir de dos punteros a BigInteger (aunque se piden dos punteros "void" para evitar desbordamientos de memoria).
De estos dos punteros, lo primero que hay que hacer es validar que realmente sean BigInteger.
¿Cómo lo validamos? La verdad es que costó encontrar una manera óptima de realizar las validaciones, sobre todo debido a que no podemos tomar el riesgo de hacer un cast directo de void a BigInteger, si lo que pretendemos es validar si es un BigInteger (básicamente, sería como validar si un cilindro rojo es dinamita mediante arrojarla al fuego).
Vamos a dejar esta parte de momento, ya que en próximas entradas trataremos la validación de datos.
Hay que tener en cuenta que la mayoría de operaciones funcionan como en lenguaje ASM. En este caso, la suma "add(a, b)" se podría entender como "a = a + b"
Siguiendo con la suma, una vez pasada la validación de datos, entramos en lo que sería la suma en sí.
Lo primero que hacemos es crear dos BigInteger temporales, sobre los que copiamos los punteros de entrada (que ya hemos verificado que son seguros para usar).
Tras esto, calculamos el signum de los BigInteger, y normalizamos los datos.
Antes de seguir, vamos a explicar en un santiamén qué es signum y la normalización (dos conceptos internos que se usan en todas las operaciones de BigInteger.
El signum es un dato significativo que indica la distribución de signos de ambos operandos. Supongamos que nuestros dos BigInteger a sumar (o simplemente, a operar) son "a" y "b"; los posibles signum serían:
| Signo de "a" | Signo de "b" | Signum |
| Positivo | Positivo | 0 |
| Positivo | Negativo | 1 |
| Negativo | Positivo | 10 |
| Negativo | Negativo | 11 |
En cuanto a la normalización, es una operación que se realiza sobre los operandos para poder trabajar con ellos de manera más cómoda, y cada tipo de operación tiene su propia configuración de normalización.
Para la suma, la normalización es la siguiente
- Signum 0: No cambian los operandos.
- Signum 1: Se cambia el signo del segundo operando.
- Signum 10: Se cambia el signo del primer operando.
- Signum 11: Se cambia el signo de ambos operandos.
A fin de cuentas, lo que conseguimos es que ambos operandos tengan un valor positivo.
Una vez con los datos normalizados, se realiza la operación con los datos, de manera que si ambos operandos comparten signo (signum 0 u 11) se realizan sumas parciales, y en caso contrario se realizan restas parciales (esta operación la veremos en próximas entradas).
Finalmente, si el segundo operando tiene signo negativo (signum 10 u 11), se cambia el signo de nuevo para reestablecer los cambios anteriores, se copia el resultado al primer operando, y se libera la memoria.
Ahora que hemos explicado el funcionamiento global, vamos a las sumas parciales (las restas ya las veremos a su tiempo).
Para las sumas parciales se procede del siguiente modo:
- Al inicio, se crean dos BigInteger temporales, y se copian los parámetros de entrada sobre ellos.
- Primero, se calcula cuál de los dos operandos tiene mayor cantidad de dígitos.
- Acto seguido, se suman los datos comunes.
- Si el segundo operando tiene más dígitos que el primero, arrastramos esos datos al primero.
- Reajustamos la longitud del primer operando, si ha habido arrastre.
- Gestionamos el acarreo.
- Copiamos el dato temporal a la salida.
- Liberamos memoria.
De nuevo, surge otro concepto: la gestión del acarreo. Debido a la arquitectura de BigInteger, se espera que cada posición de BigInteger.n tenga un valor comprendido entre {-9, 9}, por lo que, tras las sumas parciales, hay que revisar que esto se cumpla.
A nivel explicativo, funciona como una suma "tradicional", con el clásico "y me llevo una", pero aplicado de manera masiva.
La función de gestión de acarreo va recorriendo inicialmente desde 0 hasta BigInteger.count (es decir, del número con menos carga hasta el número con mayor carga) en busca de posiciones de BigInteger.n con valor superior a 9 (recordemos que el número será nomalizado y por tanto nunca habrá números negativos).
En caso de encontrar un número mayor a 9, se obtienen cociente (las "que nos llevamos") y resto (el valor que quedará), y modificamos la posición de BigInteger.n.
Esta operación se repite hasta que no se haya producido ningún acarreo.
Como optimización, cuando se produce el primer acarreo, guardamos la posición para seguir desde la siguiente en la próxima validación de acarreo, pues todas las posiciones anteriores están ya validadas.
Ya que una imagen vale más que mil palabras, os dejo un par de gráficos describiendo el funcionamiento global de "add", y el funcionamiento interno de "addition" y "carryAdd".
En esta segunda imagen podemos ver el porqué de los datos comunes (azul) y no comunes (verdes), así como el acarreo (pasamos de "14" a "4", y de "13" a "3").
La próxima entrega... ¡Restas!
¡Nos vemos!
No hay comentarios:
Publicar un comentario