BigInteger - Identificación de puntos paralelos y críticos: Suma de BigInteger

¡Hola de nuevo!

¿Qué tal lo lleváis? Vamos a seguir con el análisis de puntos críticos de la arquitectura BigInteger.

En esta ocasión, vamos a analizar los puntos críticos de la suma.

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

¡Vamos allá!

Como ya se explicó entradas atrás, la suma de BigInteger está dividida en varias funciones.

Todo el código involucrado en la suma es el siguiente:

[code lan=gral] /* * Función pAdd. Usar para sumar dos números. * * Realiza la operación de suma, teniendo en cuenta los signos de los números. * * Si los signos son iguales, hace una suma, sino, una resta. */ static void pAdd(void *va, void *vb){ struct BigInteger* a = (struct BigInteger*)malloc(sizeof(struct BigInteger)); struct BigInteger* b = (struct BigInteger*)malloc(sizeof(struct BigInteger)); if (a == NULL || b == NULL) showError(4); memcpy(a, va, sizeof(struct BigInteger)); memcpy(b, vb, sizeof(struct BigInteger)); int sig = signum(a->n[a->count], b->n[b->count]); //normalizamos los operandos if(sig == 10) //a negativo, b positivo. Cambiamos el signo de "a" y hacemos suma a->n[a->count] *= -1; else if (sig == 1) //b negativo, a positivo. Cambiamos el signo de "b" y hacemos suma b->n[b->count] *= -1; else if (sig == 11){ //a negativo, b negativo. Cambiamos signos y hacemos suma a->n[a->count] *= -1; b->n[b->count] *= -1; } //si ambos signos son iguales, se suma, sino, se resta if (sig == 0 || sig == 11) addition(a, b); else pSub(a, b); if(sig == 10 || sig == 11) //en estos casos, siempre se le va la vuelta al signo a->n[a->count] *= -1; //ajustamos el resultado memcpy(va, a, sizeof(struct BigInteger)); //liberamos memoria free(a); free(b); } /* * Función add. Usar para sumar dos números. * * Realiza la operación de suma, teniendo en cuenta los signos de los números. * * Si los signos son iguales, hace una suma, sino, una resta. */ void add(void *va, void *vb){ //validamos los datos antes de tratarlos validateBI(va); validateBI(vb); //delegamos en la función estática pAdd(va, vb); } /* * Función addition. * * Simula la operación a = a + b */ static void addition(void* va, void* vb) { struct BigInteger* a = (struct BigInteger*)malloc(sizeof(struct BigInteger)); struct BigInteger* b = (struct BigInteger*)malloc(sizeof(struct BigInteger)); int limit; int min; int move; int i; if (a == NULL || b == NULL) showError(5); memcpy(a, va, sizeof(struct BigInteger)); memcpy(b, vb, sizeof(struct BigInteger)); //asumimos que a tiene la mayor longitud limit = a->count; //asumimos que b tiene la menor longitud min = b->count; //indicador de necesidad de arrastre move = 0; i = 0; //si no es así, rectificamos if(b->count > limit){ limit = b->count; min = a->count; move = 1; } //sumamos los dígitos que coinciden for(;i <= min;i++) a->n[i] += b->n[i]; //los dígitos que no coinciden los traspasamos if(move == 1){ for(;i >= limit;i++) a->n[i] = b->n[i]; a->count = limit; } //gestionamos el acarreo carryAdd(a); //ajustamos resultado memcpy(va, a, sizeof(struct BigInteger)); //liberamos memoria free(a); free(b); } /* * Función carryAdd. * * Gestiona el acarreo de la suma. Si hay movimiento de datos, se mueve el * valor 1 a ret. * * De esta manera, podemos llamar hasta que no haya cambios en el acarreo. */ static void carryAdd(void* va) { int i = 0; int acc; struct BigInteger* a = (struct BigInteger*)malloc(sizeof(struct BigInteger)); if (a == NULL) showError(6); memcpy(a, va, sizeof(struct BigInteger)); acc = 0; //recorremos a y vamos sumando el acarreo for(;i <= a->count; i++){ //sumamos acarreo a->n[i] += acc; //como acc es int, podemos dividir entre 10 y sacar el acarreo acc = a->n[i] / 10; if (acc > 0) //normalizamos el número a->n[i] = a->n[i] % 10; } //si ha quedado acarreo, lo guardamos al final; if (acc > 0) { if (a->count == MAX_LENGTH) showError(1); else a->n[++a->count] = acc; } //ajustamos resultado memcpy(va, a, sizeof(struct BigInteger)); //liberamos memoria free(a); } [/code]

A grandes rasgos, la función que a la que se llamaría sería "add". Como ya explicamos, se hará la validación, se obtendrá el signum (ya en pAdd) y se normalizarán los datos, y se pasará a hacer la suma dígito a dígito (en addition).

Finalmente se gestiona el acarreo y se libera memoria.

Bien, pues un análisis de puntos críticos mostraría el siguiente esquema:

La validación de "a" y la validación de "b" se pueden hacer en paralelo (hemos marcado con línea continua, porque la llamada a "validateBI" sería única, y ya veremos cómo se gestiona esta función), ya que en caso de haber un dato erróneo, la ejecución se interrumpe.

Como siempre que hay trabajo paralelo, ponemos un semáforo, y empezamos a trabajar en la normalización.

Una vez llegado el momento de sumar dígito a dígito (addition), podemos abrir dos hilos de clústeres, que sumen la parte común y muevan la parte no común. Ya que la suma se hace posición a posición, y de momento no hay acarreo, se puede hacer totalmente en paralelo, y por tanto, este es un buen punto de optimización.

De nuevo, esperamos a tener la suma completa antes de pasar al acarreo.

Lamentablemente, el acarreo no puede paralelizarse, ya que cada dígito puede ser modificado por el anterior, y por tanto, no se puede paralelizar... Supongamos que en la posición "i" tenemos un "1", y en "i + 1" tenemos un "9": no podemos decir que un "i" normalizado valdrá "1" porque no hay acarreo, ya que si "i + 1" consumiera un acarreo, generaría un nuevo acarreo.

Así, como podéis ver, en la función de la suma estaríamos convirtiendo "n" sumas en una sola, a parte de la gestión del acarreo.

Podemos ver cómo la suma de dígitos es identificada por Visual Studio como un punto de consumo de CPU (en este caso, tras hacer 10.000 sumas de BigInteger). En este caso, supondría bajar un 0,25% el consumo de la suma, lo cual a priori no parece demasiado, pero tengamos en cuenta que esta función se llama desde varios sitios (multiplicación, potencias, raíces, ...)

Bueno, amigos, de momento esto es todo para esta entrada.

¡Nos vemos!