BigInteger - Funciones auxiliaries

Hola de nuevo!

En esta entrada, vamos a seguir ahondando en la arquitectura de BigInteger.

En este caso, vamos a revisar las funciones auxiliares de BigInteger.

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

¡Vamos allá!

Hay una serie de funciones auxiliares en BigInteger, que sirven de apoyo a los desarrolladores y/o ejercen funciones intermedias.

Actualmente, la lista de funciones auxiliares son:

1. Funciones auxiliares
1. Valores frecuentes
2. Comparación
3. Anexar
4. Display
5. Validación de datos

A continuación, haremos un breve recorrido por el funcionamiento de cada una de las funciones.

Valores frecuentes

Se basa en la función ""BImemcpy", que es una extensión de "memcpy".

Básicamente, existen unas variables estáticas en BigInteger, que almacenan unos valores fijos, y a través de "BImemcpy" se puede copiar ese valor a una variable destino.

Los valores frecuentes son:

• Cero
• Uno
• Diez
• Cien 
• Menos uno

Para copiar estos valores a un BigInteger, basta con llamar a "BImemcpy(BI_Destino, valor)", siendo "valor" un int con valor 0, 1, 10, 100, -1.

Comparación

La función de comparación (equals) compara el valor de dos BigInteger, y devuelve un valor int que apunta hacia el número más grande.

• Si a > b: Retorno 1
• Si a = b: Retorno 0
• Si a < b: Retorno 2

La función tiene un mínimo de complejidad, ya que debe ser capaz de trabajar con números negativos.

El funcionamiento está basado en comparar número a número, teniendo en cuenta el signo, como decía antes.

Así, la función primero valida los datos a comparar, y los mueve a variables temporales.

Una vez copiados, obtenemos el signum, y hacemos unas validaciones rápidas.

• Si el signum es 1: Significa que "a >= 0", y "b < 0", por tanto "a > b". Retornamos 1.
• Si el signum es 10: Significa que "a < 0", y "b >= 0", por tanto "a < b". Retornamos 2.
• En cualquier otro caso, comparamos.

En el caso de tener que comparar, también hay ciertas optimizaciones, en base a la longitud de "a" y "b".

• Si "a.count < b.count": Significa que  |a| < |b|. El retorno es 2
• Si "a.count > b.count": Significa que |a| > |b|. El retorno es 1
• Si "a.count = b.count": Se compara dígito a dígito

Hay que tener en cuenta un punto importante. Estamos comparando valores absolutos, ya que en estos casos ambos BigInteger tienen el mismo signo (y ya nos encargamos de ello luego).

En caso de tener el mismo número de dígitos, comparamos dígito a dígito, pero en el orden inverso del array, es decir, desde el dígito con más peso hacia el de menos peso. En este caso, se itera hasta que el dígito de "a" y el dígito de "b" son distintos. En ese caso, se compara, se guarda el retorno, y se deja de iterar.

Finalmente, si el signum es 11, se invierte el retorno (se mueve 1 si era 2, y se mueve 2 si era 1).

Liberamos memoria, y ajustamos el retorno.

Anexar

Esta función sirve para unir dos BigInteger. Es decir, si tenemos un BigInteger con valor "1", y otro con valor "2", podemos obtener un BigInteger con valor "12".

Para hacer esto, como en tantas otras funciones, se validan los datos de entrada, y se mueven a datos temporales.

Seguidamente, se van moviendo consecutivamente los datos, pero, OJO, debido a la arquitectura, se anexan en orden inverso... Es decir, si queremos anexar "1" y "2" para obtener "12", tenemos que enviarlos como "2", "1".

El anexar los datos se hace mediante la creación de un valor intermedio con la parte final seguida de tantos "0" como longitud tenga la parte inicial, y seguidamente se suman.

Display

Esta función sirve para mover los datos de BigInteger a un puntero a char, de manera que se pueda usar, por ejemplo, en un printf.

Para esta función, primero se validan los datos, y se copian los datos a una variable temporal.

Seguidamente, se valida si el dígito "BigInteger.n[BigInteger.count]" (es decir, el dígito con más peso del número) es negativo; en caso de serlo, se normaliza y se mueve un "-" al primer caracter del char*.

Después, se itera desde BigInteger.count hasta 0 (esto es, en orden inverso), y se van añadiendo caracteres al char*; esto se consigue haciendo un cast de int a char y sumando 48 al valor puntual de BigInteger (esto se hace porque el código ASCII de los números empieza en la posición 48).

Finalmente, se añade el delimitador '\0', y se libera la memoria.

Validación de datos

Y llegamos a la función de la que más referencias hemos hecho... la validación de datos.

Esta función trabaja íntegramente con lógica de punteros; es decir, las sumas se hacen a las direcciones de memoria, no al contenido de las variables. Hacemos esto aprovechando que BigInteger se compone exclusivamente de valores int.

Inicialmente, creamos un valor int temporal, al que llamaremos "t".

Copiamos el tamaño de un int del BigInteger a validar a "t", y validamos que esté entre "0" y la longitud máxima de BigInteger (MAX_LENGTH).

Llegados a este punto, hemos validado la longitud de BigInteger; queda el array de datos.

Copiamos el tamaño de un int de "a + 1" a "t" (recordad, aquí estamos moviendo una posición de memoria el puntero de "a".

Iteramos, desde 0 hasta MAX_LENGTH, y vamos validando que "t" tenga un valor entre -9 y 9. Después de cada validación, copiamos el tamaño de un int de "a + i + 1)  a "t".

En caso que alguna validación no se cumpla, el programa se para; si llegamos al final, liberamos memoria y terminamos la validación.

Y hasta aquí las funciones auxiliares! Con esto, y un par de novedades que quedan por contar (cambios que he introducido a medida que "releía" el código, habremos terminado la parte fácil de la arquitectura. 

Nos quedará por discutir la paralelización, y la parte más divertida, que será hacer la implementación :)

¡Nos vemos!