¿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.
¡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
[code lan=gral]
/*
* Función pSub. Usar para restar dos números.
*
* Simula la operación a = a - b.
*
* Si len(a) < len(b), se intercambian los valores
*/
static void pSub(void* va, void *vb){
int sig;
int comp;
struct BigInteger* a =
(struct BigInteger*)malloc(sizeof(struct BigInteger));
struct BigInteger* b =
(struct BigInteger*)malloc(sizeof(struct BigInteger));
if (a == NULL || b == NULL)
showError(7);
memcpy(a, va, sizeof(struct BigInteger));
memcpy(b, vb, sizeof(struct BigInteger));
hardEquals(a, b, &comp);
sig = signum(a->n[a->count], b->n[b->count]);
//si ambos son negativos, comp = 1 significa a < b
if((comp == 2 && sig < 11) || (comp == 1 && sig == 11)){
pSub(b, a);
//cambiamos el signo
b->n[b->count] *= -1;
//reasignamos
memcpy(a, b, sizeof(struct BigInteger));
}else if(comp == 0){
a->n[0] = 0;
a->count = 0;
}else{
//normalizamos los signos
if(sig == 1)
b->n[b->count] *= -1;
else if(sig == 10)
a->n[a->count] *= -1;
else if(sig == 11){
a->n[a->count] *= -1;
b->n[b->count] *= -1;
}
//si tienen el mismo signo, se resta, sino se suma
if(sig == 0 || sig == 11)
subtract(a, b);
else
pAdd(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 sub. Usar para restar dos números.
*
* Simula la operación a = a - b.
*
* Si len(a) < len(b), se intercambian los valores
*/
void sub(void *va, void *vb) {
//validamos los punteros antes de tratarlos
validateBI(va);
validateBI(vb);
//delegamos en la función estática
pSub(va, vb);
}
/*
* Función subrtact.
*
* Realiza la resta.
*/
static void subtract(void *va, void *vb){
int i = 0;
int accType = 0;
struct BigInteger* a =
(struct BigInteger*)malloc(sizeof(struct BigInteger));
struct BigInteger* b =
(struct BigInteger*)malloc(sizeof(struct BigInteger));
if (a == NULL || b == NULL)
showError(8);
memcpy(a, va, sizeof(struct BigInteger));
memcpy(b, vb, sizeof(struct BigInteger));
//restamos los dígitos comunes
for(;i <= b->count;i++)
a->n[i] -= b->n[i];
//si el último dígito es negativo
if(a->n[a->count] < 0)
accType = 1;
carrySub(a, accType);
//movemos el resultado
memcpy(va, a, sizeof(struct BigInteger));
//liberamos memoria
free(a);
free(b);
}
/*
* Función carrySub.
*
* Gestiona el acarreo de la resta. Si carryType = 0, el acarreo
* se gestiona como a = 10 + a;
* sino, se invierte el signo (excepto al último dígito)
*/
static void carrySub(void *va, int carryType){
int i = 0;
int acc = 0;
struct BigInteger* a =
(struct BigInteger*)malloc(sizeof(struct BigInteger));
if (a == NULL)
showError(9);
memcpy(a, va, sizeof(struct BigInteger));
if(carryType == 0){
for(;i <= a->count; i++){
//restamos el acarreo al número
a->n[i] -= acc;
if(a->n[i] < 0){
//normalizamos el número
a->n[i] += 10;
acc = 1;
}else
acc = 0;
}
}else{
//en esta opción, no es necesario pasar una segunda vez por acarreos.
for(i = 0;i < a->count;i++)
if(a->n[i] < 0)
//normalizamos el número
a->n[i] = a->n[i] * -1;
}
//contamos de nuevo los dígitos
recount(a);
//ajustamos el resultado
memcpy(va, a, sizeof(struct BigInteger));
//liberamos memoria
free(a);
}
/*
* Función recount.
*
* Recuenta las cifras, para ver si hay que disminuir el conteo.
*/
static void recount(void *va){
struct BigInteger* a =
(struct BigInteger*)malloc(sizeof(struct BigInteger));
if (a == NULL)
showError(10);
memcpy(a, va, sizeof(struct BigInteger));
while(a->n[a->count--] == 0);
++a->count;
if(a->count < 0)
a->count = 0;
//ajustamos el resultado
memcpy(va, a, sizeof(struct BigInteger));
//liberamos memoria
free(a);
}
[/code]
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:
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!
No hay comentarios:
Publicar un comentario