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:

Get Raw

0001/*

0002 * Función pAdd. Usar para sumar dos números.

0003 *

0004 * Realiza la operación de suma, teniendo en cuenta los signos de los números.

0005 *

0006 * Si los signos son iguales, hace una suma, sino, una resta.

0007 */

0008static void pAdd(void *va, void *vb){

0009  struct BigInteger* a = 

0010      (struct BigInteger*)malloc(sizeof(struct BigInteger));

0011  struct BigInteger* b = 

0012      (struct BigInteger*)malloc(sizeof(struct BigInteger));

0013 

0014  if (a == NULL || b == NULL)

0015    showError(4);

0016 

0017  memcpy(a, va, sizeof(struct BigInteger));

0018  memcpy(b, vb, sizeof(struct BigInteger));

0019 

0020  int sig = signum(a->n[a->count], b->n[b->count]);

0021 

0022  //normalizamos los operandos

0023  if(sig == 10)

0024    //a negativo, b positivo. Cambiamos el signo de "a" y hacemos suma

0025    a->n[a->count] *= -1;

0026  else if (sig == 1)

0027    //b negativo, a positivo. Cambiamos el signo de "b" y hacemos suma

0028    b->n[b->count] *= -1;

0029  else if (sig == 11){

0030    //a negativo, b negativo. Cambiamos signos y hacemos suma

0031    a->n[a->count] *= -1;

0032    b->n[b->count] *= -1;

0033  }

0034 

0035  //si ambos signos son iguales, se suma, sino, se resta

0036  if (sig == 0 || sig == 11)

0037    addition(a, b);

0038  else 

0039    pSub(a, b);

0040 

0041  if(sig == 10 || sig == 11)

0042    //en estos casos, siempre se le va la vuelta al signo

0043    a->n[a->count] *= -1;

0044 

0045  //ajustamos el resultado

0046  memcpy(va, a, sizeof(struct BigInteger));

0047 

0048  //liberamos memoria

0049  free(a);

0050  free(b);

0051}

0052 

0053/*

0054 * Función add. Usar para sumar dos números.

0055 *

0056 * Realiza la operación de suma, teniendo en cuenta los signos de los números.

0057 *

0058 * Si los signos son iguales, hace una suma, sino, una resta.

0059 */

0060void add(void *va, void *vb){

0061  //validamos los datos antes de tratarlos

0062  validateBI(va);

0063  validateBI(vb);

0064 

0065  //delegamos en la función estática

0066  pAdd(va, vb);

0067}

0068 

0069/*

0070 * Función addition.

0071 *

0072 * Simula la operación a = a + b

0073 */

0074static void addition(void* va, void* vb) {

0075  struct BigInteger* a = 

0076      (struct BigInteger*)malloc(sizeof(struct BigInteger));

0077  struct BigInteger* b = 

0078      (struct BigInteger*)malloc(sizeof(struct BigInteger));

0079  int limit;

0080  int min;

0081  int move;

0082  int i;

0083 

0084  if (a == NULL || b == NULL)

0085    showError(5);

0086 

0087  memcpy(a, va, sizeof(struct BigInteger));

0088  memcpy(b, vb, sizeof(struct BigInteger));

0089 

0090  //asumimos que a tiene la mayor longitud

0091  limit = a->count;

0092 

0093  //asumimos que b tiene la menor longitud

0094  min = b->count;

0095 

0096  //indicador de necesidad de arrastre

0097  move = 0;

0098  i = 0;

0099 

0100  //si no es así, rectificamos

0101  if(b->count > limit){

0102    limit = b->count;

0103    min = a->count;

0104    move = 1;

0105  }

0106 

0107  //sumamos los dígitos que coinciden

0108  for(;i <= min;i++)

0109    a->n[i] += b->n[i];

0110 

0111  //los dígitos que no coinciden los traspasamos

0112  if(move == 1){

0113    for(;i >= limit;i++)

0114      a->n[i] = b->n[i];

0115 

0116    a->count = limit;

0117  }

0118 

0119  //gestionamos el acarreo

0120  carryAdd(a);

0121 

0122  //ajustamos resultado

0123  memcpy(va, a, sizeof(struct BigInteger));

0124 

0125  //liberamos memoria

0126  free(a);

0127  free(b);

0128}

0129 

0130/*

0131 * Función carryAdd.

0132 *

0133 * Gestiona el acarreo de la suma. Si hay movimiento de datos, se mueve el 

0134 * valor 1 a ret.

0135 *

0136 * De esta manera, podemos llamar hasta que no haya cambios en el acarreo.

0137 */

0138static void carryAdd(void* va) {

0139  int i = 0;

0140  int acc;

0141  struct BigInteger* a = 

0142      (struct BigInteger*)malloc(sizeof(struct BigInteger));

0143 

0144  if (a == NULL)

0145    showError(6);

0146 

0147  memcpy(a, va, sizeof(struct BigInteger));

0148 

0149  acc = 0;

0150 

0151  //recorremos a y vamos sumando el acarreo

0152  for(;i <= a->count; i++){

0153    //sumamos acarreo

0154    a->n[i] += acc;

0155 

0156    //como acc es int, podemos dividir entre 10 y sacar el acarreo

0157    acc = a->n[i] / 10;

0158 

0159    if (acc > 0) 

0160      //normalizamos el número

0161      a->n[i] = a->n[i] % 10;

0162  }

0163 

0164  //si ha quedado acarreo, lo guardamos al final;

0165  if (acc > 0) {

0166    if (a->count == MAX_LENGTH)

0167      showError(1);

0168    else 

0169      a->n[++a->count] = acc;

0170  }

0171 

0172  //ajustamos resultado

0173  memcpy(va, a, sizeof(struct BigInteger));

0174 

0175  //liberamos memoria

0176  free(a);

0177}

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!