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

Bienvenidos un día más!

¿Cómo os trata el verano? Espero que estés bien fresquitos y a la sombra :-)

Yo por mi parte estoy bastante contento, ya que todavía estamos a Julio y este año ya es el tercero con más entradas en el blog! Me alegra ver que poco a poco he ido retomando la escritura, siendo que incluso en 2018 estuve todo el año sin escribir...

En fin, vamos a entrar en materia... vamos a seguir con la identificación de puntos críticos en la arquitectura BigInteger para realizar la paralelizazión.

En esta entrada, trataremos la resta.

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

¡Vamos allá!

Como ya vimos, la resta de BigInteger tenía un funcionamiento muy similar a la suma, pero estaba diseñada de manera que siempre contábamos con "a >= b".

Por eso, veréis que la identificación de puntos críticos es menor que en la suma, pero el beneficio es el mismo.

Todo el código relacionado con la resta, es el siguiente

Get Raw

0001/*

0002 * Función pSub. Usar para restar dos números.

0003 *

0004 * Simula la operación a = a - b.

0005 *

0006 * Si len(a) < len(b), se intercambian los valores

0007 */

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

0009  int sig;

0010  int comp;

0011  struct BigInteger* a = 

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

0013  struct BigInteger* b = 

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

0015 

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

0017    showError(7);

0018 

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

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

0021 

0022  hardEquals(a, b, &comp);

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

0024 

0025  //si ambos son negativos, comp = 1 significa a < b

0026  if((comp == 2 && sig < 11) || (comp == 1 && sig == 11)){

0027    pSub(b, a);

0028 

0029    //cambiamos el signo

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

0031 

0032    //reasignamos

0033    memcpy(a, b, sizeof(struct BigInteger));

0034  }else if(comp == 0){

0035    a->n[0] = 0;

0036    a->count = 0;

0037  }else{

0038    //normalizamos los signos

0039    if(sig == 1)

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

0041    else if(sig == 10)

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

0043    else if(sig == 11){

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

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

0046    }

0047 

0048    //si tienen el mismo signo, se resta, sino se suma

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

0050      subtract(a, b);

0051    else 

0052      pAdd(a, b);

0053 

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

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

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

0057  }

0058 

0059  //ajustamos el resultado

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

0061 

0062  //liberamos memoria

0063  free(a);

0064  free(b);

0065}

0066 

0067/*

0068 * Función sub. Usar para restar dos números.

0069 *

0070 * Simula la operación a = a - b.

0071 *

0072 * Si len(a) < len(b), se intercambian los valores

0073 */

0074void sub(void *va, void *vb) {

0075  //validamos los punteros antes de tratarlos

0076  validateBI(va);

0077  validateBI(vb);

0078 

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

0080  pSub(va, vb);

0081}

0082 

0083/*

0084 * Función subrtact.

0085 *

0086 * Realiza la resta.

0087 */

0088static void subtract(void *va, void *vb){

0089  int i = 0;

0090  int accType = 0;

0091  struct BigInteger* a = 

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

0093  struct BigInteger* b = 

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

0095 

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

0097    showError(8);

0098 

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

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

0101 

0102  //restamos los dígitos comunes

0103  for(;i <= b->count;i++)

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

0105 

0106  //si el último dígito es negativo

0107  if(a->n[a->count] < 0)

0108    accType = 1;

0109 

0110  carrySub(a, accType);

0111 

0112  //movemos el resultado

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

0114 

0115  //liberamos memoria

0116  free(a);

0117  free(b);

0118}

0119 

0120/*

0121 * Función carrySub.

0122 *

0123 * Gestiona el acarreo de la resta. Si carryType = 0, el acarreo

0124 * se gestiona como a = 10 + a; 

0125 * sino, se invierte el signo (excepto al último dígito)

0126 */

0127static void carrySub(void *va, int carryType){

0128  int i = 0;

0129  int acc = 0;

0130  struct BigInteger* a = 

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

0132 

0133  if (a == NULL)

0134    showError(9);

0135 

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

0137 

0138  if(carryType == 0){

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

0140      //restamos el acarreo al número

0141      a->n[i] -= acc;

0142 

0143      if(a->n[i] < 0){

0144        //normalizamos el número

0145        a->n[i] += 10;

0146        acc = 1;

0147      }else

0148        acc = 0;

0149    }

0150  }else{

0151    //en esta opción, no es necesario pasar una segunda vez por acarreos.

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

0153      if(a->n[i] < 0)

0154        //normalizamos el número

0155        a->n[i] = a->n[i] * -1;

0156  }

0157 

0158  //contamos de nuevo los dígitos

0159  recount(a);

0160 

0161  //ajustamos el resultado

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

0163 

0164  //liberamos memoria

0165  free(a);

0166}

0167 

0168/*

0169 * Función recount.

0170 *

0171 * Recuenta las cifras, para ver si hay que disminuir el conteo.

0172 */

0173static void recount(void *va){

0174  struct BigInteger* a = 

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

0176 

0177  if (a == NULL)

0178    showError(10);

0179 

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

0181 

0182  while(a->n[a->count--] == 0);

0183 

0184  ++a->count;

0185 

0186  if(a->count < 0)

0187    a->count = 0;

0188 

0189  //ajustamos el resultado

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

0191 

0192  //liberamos memoria

0193  free(a);

0194}

Como se puede ver, en este caso hay alguna que otra función más (recount, por ejemplo), y como ya anticipamos en su día, la comparación la vamos a obviar (ya que tiene su propia entrada reservada).

La distribución de puntos críticos sería la siguiente:

Como ya sucedía con la suma, la validación de "a" y "b" puede realizarse en dos hilos independientes (para aclarar, se "malgastarían" dos clústeres de 16 hilos para paralelizar la validación de ambos operandos; "perdemos" 30 hilos, pero tardamos la mitad en validar los datos).

Seguidamente, podemos obtener el signum y comparar los operandos al mismo tiempo, para, tras pasar el semáforo, normalizar los datos.

Una vez llegados a este punto, haríamos la resta de dígitos comunes (no hace falta revisar los no comunes ya que "a >= b"), y pasados el semáforo, haríamos el acarreo y recuento de dígitos.

A tener en cuenta, el acarreo lo hemos marcado de manera distinta ya que en ciertas ocasiones sí se puede paralelizar (cuando carryType == 1), por lo que será decisión de la función "carrySub" aplicar la lógica necesaria y los semáforos pertinentes.

Con estos cambios, el coste de la resta se reduciría significativamente, ya que podemos asumir que la resta dígito a dígito tendrá el coste de la resta de un dígito; también se reduce el coste de validación, de momento, a la mitad (y ya veremos el análisis de su función), y podemos obviar el coste de calcular el signum (ya que la comparación tendrá un coste mayor, aunque el coste del cálculo del signum es marginal).

Y con esto nos despedimos por ahora. En próximas entregas, pasamos a las operaciones complejas (multiplicación y división), ¡que serán súper entretenidas de analizar!

¡Nos vemos!