Hola de nuevo!
Pues seguimos dando la tabarra con la arquitectura BigInteger.
En este caso, vamos a entrar en la operación de multiplicación de BigInteger.
¡Vamos allá!
La operación de multiplicación empieza como el resto de operaciones: validando ambos operandos; no obstante, aquí terminan prácticamente las similitudes con las operaciones vistas hasta ahora (suma de BigInteger, y resta de BigInteger), debido a que la multiplicación de BigInteger es una operación de segundo rango, es decir, en definitiva, una multiplicación es un conjunto de sumas (aunque no tratamos las multiplicaciones como sucesivas sumas en BigInteger).
Esta función (así como la división), utilizan una estructura auxiliar denominada BIT (BigInteger Table), que sirve como buffer, una especie de "tabla de multiplicar"; llegado el momento, explicaremos cómo se utiliza y porqué.
Para multiplicar dos BigInteger, primero se reserva espacio para dos BigInteger temporales (como siempre), y también se reserva espacio para un array de b.count posiciones, así como para una estructura BIT.
Como podéis pensar (con razón) es la cantidad de datos que la multiplicación gestiona... bien, si nuestro BigInteger tiene 4096 posiciones (+1 int adicional para count), podemos asumir que, como máximo, el array tendrá 4096 BigInteger's, lo que en este caso serían un total de aproximadamente 40mb de memoria... ¿verdad que parecía más?
Bueno, tras la pequeña reflexión, seguimos. Tras reservar la memoria, realizamos una serie de comparaciones para evitar cálculos triviales:
| Dato a comparar | Comparar con | Acción si son iguales |
| a | 0 | resultado = 0 |
| b | 0 | resultado = 0 |
| |a| | 1 | resultado = b |
| |b| | 1 | resultado = a |
Por otra parte, se realiza la normalización de datos (concretamente, se hace tras validar si "a" o "b" son 0, y antes de validar si "|a|" o "|b|" son 1), de la siguiente manera:
- Si el signum es 0: No realizar ninguna acción.
- Si el signum es 1: Cambiar el signo de "b".
- Si el signum es 10: Cambiar el signo de "a".
- Si el signum es 11: Cambiar el signo de "a" y "b".
Llegados este punto, es el momento en el que entra en juego BIT. Como hemos anticipado, BIT funciona como una especie de "tabla de multiplicar", en la que vamos almacenando los resultados parciales de manera dinámica.
Inicialmente, se establece que:
- BIT[0] = 0
- BIT[1] = a
Estos resultados parciales no deben confundirse con los productos parciales: los resultados parciales son siempre un número finito entre 0 y 9, y son los resultados de multiplicar "a" por un número de un dígito (de ahí la referencia a una "tabla de multiplicar); por otra parte, un producto parcial es el resultado de multiplicar una cifra de "b" por "a".
El resultado de un producto parcial siempre será un resultado parcial.
Puede parecer (y lo es) algo confuso, pero ya se irá clarificando a medida que se explica.
Siguiendo con la multiplicación, si no es ninguno de los casos contemplados en la tabla, se pasa a realizar los productos parciales, iterando sobre cada dígito de b, del siguiente modo
- ¿Existe un valor para BIT[b.n[actual]]?
- Sí: El resultado parcial para este dígito es BIT[b.n[actual]]
- No: Se calcula el resultado parcial a * b.n[actual] y se almacena en BIT[b.n[actual]]
- Se genera un offset para el resultado parcial usando el dígito actual, para añadir tantos 0 a la izquierda (a la derecha, internamente), y se almacena en el array de resultados parciales
El cálculo de un producto parcial se realiza multiplicando cada cifra de "a" por la cifra seleccionada de "b", tras lo que se hace una gestión de acarreo para normalizar el número.
La generación del offset se puede presentar gráficamente de la siguiente manera:
En este caso, el offset tendría un valor de 2, es decir, estaríamos trabajando con la tercera cifra de la multiplicación. Si lo plasmamos dentro de un contexto completo, sería algo como:
7165
x 123
--------
21495
143300
716500
--------
881295
En este caso:
- Los "0" marcados en negrita serían parte del offset.
- BIT tendrá los siguientes valores:
- BIT[0] = 0
- BIT[1] = 7165
- BIT[2] = 14330
- BIT[3] = 21495
- Los resultados parciales serían:
- 21495
- 143300
- 716500
Tras la explicación, que espero sirva para clarificar al máximo los conceptos, seguimos con la multiplicación.
En este punto, tenemos un array con "b.count" posiciones, conteniendo los resultados parciales, así que lo suyo es sumar de manera secuencial estos valores.
Realmente, no importa el orden en que se sumen los valores, ya que el orden de los factores no altera el resultado.
Es decir, siguiendo con nuestro ejemplo... daría lo mismo operar "21495 + 143300 + 716500" que "14330 + 21495 + 716500"; el resultado siempre será el mismo.
Estas sumas se realizan a través de la función estándar de suma (fun fact - aunque no es posible debido a la configuración de la arquitectura - en este caso, "a" y "b" siempre serán datos positivos - , sería plausible llegar de la multiplicación a la resta).
Finalmente, ajustamos el signo si "a" y "b" no comparten signo (signum 1 o 10), copiamos los datos a salida, y liberamos memoria.
Aunque no se ha mencionado, la generación del offset se realiza en una función dedicada, que realiza movimiento y rellenado de datos, tal como se aprecia en la imagen anterior.
A nivel global, la multiplicación se realizaría del siguiente modo:
Con el uso de BIT, se ahorra un buen tiempo de cómputo, al poder aprovechar los resultados de otras operaciones; teniendo esto en cuenta, en un número de (por ejemplo) 256 posiciones, solo se realizarán un máximo de 10 multiplicaciones + 255 sumas = 265 operaciones con BigInteger; si no tuviéramos BIT, se realizarían 256 multiplicaciones + 255 sumas = 511 operaciones con BigInteger.
Y para terminar, el algoritmo completo de la multiplicación, sería el siguiente:
Como podéis ver, la cosa se va complicando en estas operaciones...
Ya queda poco para terminar la sección de funciones báscias; en la próxima entrada... ¡Divisiones!
Espero que os resulte entretenido.
¡Nos vemos!
No hay comentarios:
Publicar un comentario