Ejercicio obligatorio 2
Fecha de entrega: Lunes 5 de mayo
Introducción
Más allá del BCD
Como ya sabemos los procesadores operan sobre números binarios con una limitada cantidad de bits (32, 64, etc.) realizando operaciones entre ellos mediante circuitos electrónicos. Ahora bien, para muchas aplicaciones esta precisión no es suficiente.
En el EJ1 vimos que una manera de resolver este problema era almacenando dígitos decimales e implementando todas las operaciones aritméticas mediante algoritmos dígito a dígito. Este enfoque no es eficiente porque desaprovecha la gran potencia de cómputo en binario que tienen los procesadores.
Lo que podemos hacer para almacenar enteros de precisión arbitraria sin sacrificar eficiencia es almacenar a los mismos como un conjunto de enteros binarios y operarlos por partes.
Por ejemplo, podríamos tener dos enteros de 32 bits uint32_t n[2];
y decir que entre ambos representan un número de 64 bits tal que
\(n = 2^{32} n_1 + n_0\), n[1] es su parte alta, n[0] es su parte baja.
¿Por qué decimos que haciendo algo así podemos aprovechar las operaciones del
procesador? Por ejemplo, si tuviéramos otro número m definido de igual manera
podríamos calcular \(r = n + m\) como
Como cada una de las componentes son enteros de 32 bits podemos computar las sumas parciales vía hardware. Es sencillo ver que prácticamente nuestro resultado será \(r_0 = n_0 + m_0\) y \(r_1 = n_1 + m_1\). Entonces podríamos resolver la suma de dos números de 64 bits apenas con 2 operaciones de suma tradicionales de 32 bits. (Comparar con el enfoque del EJ1, un número de 64 bits en decimal puede ocupar hasta 20 dígitos, ¿cuántas operaciones necesitaríamos?)
Dijimos que "prácticamente nuestro resultado será", ¿por qué "prácticamente"? Porque ese resultado no es del todo correcto. Al decir eso estaríamos asumiendo que, por ejemplo, la suma \(n_0 + m_0\) entra en 32 bits y por lo tanto se puede almacenar en \(r_0\). Pero podría pasar que esta suma ocupe 33 bits y ahí eso que escribimos no funciona.
En primer lugar, ¿cómo podemos hacer para saber si la suma va a ocupar 33 bits?
En el lenguaje C los overflows ocurren, no podemos detectarlos sin ponernos a
hacer inspecciones complejas sobre el resultado. Ahora bien, actualmente todas
las computadoras son de 64 bits, es decir, operan aritméticamente de forma
nativa en 64 bits. Más allá de que m y n tengan componentes de 32 bits
nosotros podemos operarlas en 64 bits y ver si el resultado entró en 32 o
necesitó un bit adicional para ser almacenado. Es simplemente chequear si el
bit 33avo está prendido o no. Si no está prendido entonces la cuenta entró, ya
estamos.
Si estuviera prendido entonces está bien decir que \(r_0 = n_0 + m_0\) truncando ese bit adicional que no puede almacenarse en \(r_0\), ahora bien ese bit adicional, que es un acarreo, tiene que ser el "me llevo uno" en el cálculo de \(r_1\). Si tenemos un acarreo desde \(r_0\) entonces calcularemos \(r_1 = n_1 + m_1 + 1\).
¿Ya terminamos? No. Al operar dos números de 64 bits existe la chance de que el resultado ocupe 65 bits. En ese caso en \(r_1\) guardaremos la operación truncada y "nos llevaremos uno" de vuelta, el resultado tendrá un \(r_2 = 1\).
Finalmente nuestro resultado podría ser \(r = r_0 + r_1 2^{32} + r_2 2^{64}\).
Ya ahora vimos que empezamos con arreglos de 2 elementos pero podemos tener arreglos del largo que queramos. Esta operación se puede generalizar para el tamaño que necesitemos.
Si quisiéramos representar un entero de \(x\) bits podemos guardarlo en un
vector de \(x/32\) enteros uint32_t y para, por ejemplo, sumarlo iremos
operando de a pares desde los valores menos significativos y acarreando uno si
alguna de esas sumas superara los 32 bits. Finalmente podremos terminar con un
número que tenga más bits y eventualmente necesite un entero adicional.
Volviendo al inicio, lo que estamos haciendo al operar de esta forma es representar el número en base \(2^{32}\) e implementar los mismos algoritmos que aprendimos en la primaria para base 10. En nuestro caso cada dígito es un número entre 0 y 4294967295. Sumamos dígito a dígito y si nos pasamos de 4294967295 reiniciamos y nos llevamos uno.
Así como presentamos el algoritmo de la suma hay muchos otros algoritmos que podemos implementar operando los enteros de forma individual y luego propagando lo que no entre al entero siguiente.
Enteros largos
Queremos modelar una estructura que nos sirva para almacenar estos enteros de longitud arbitraria:
typedef struct {
uint32_t *d;
size_t n;
} entero_t;
que permite almacenar en memoria los n "dígitos" d de un entero:
En esta representación, al igual que siempre, d[0] es el dígito menos
significativo mientras que d[n-1] será el más significativo. Además d[n-1]
debería ser distinto de cero (si no podríamos representar el número con menos
dígitos).
Notar que sólo nos interesa representar números positivos.
Trabajo
Creación y destrucción
Se pide implementar la función auxiliar
entero_t *_crear(size_t n);
que genere la memoria necesaria para almacenar un entero de n dígitos. Los
dígitos deben ser inicializados a cero. La función debe devolver el entero
creado o NULL en caso de falla.
Se pide implementar la función void entero_destruir(entero_t *entero);
que libere la memoria asociada al entero previamente creado.
Clonación
Se pide implementar la función
entero_t *entero_clonar(const entero_t *entero) que devuelva una copia
exacta del entero recibido en memoria nueva. Debe devolver NULL en
caso de falla.
Redimensión
Se pide implementar la función auxiliar
bool _redimensionar(entero_t *entero, size_t n); que redimensione el
entero al tamaño n. Si esto implicara agregar dígitos los mismos se
inicializarán en cero. La función devuelve true si puede realizar la
operación y false en caso contrario.
Comparación
Implementar la función
int entero_comparar(const entero_t *a, const entero_t *b);. La función
devolverá 0 si \(a = b\), negativo si \(a < b\) y positivo si
\(a > b\) (como todas las funciones de comparación en C, por ejemplo
strcmp()).
Desde el dígito más pesado hacia los más livianos, si uno de esos dígitos es mayor que el otro ese será el número mayor. Los números serán iguales sólo si no hay ningún dígito que sea mayor que otro entre ambos números.
Corrimiento a derecha
Implementar la función bool entero_desplazar_derecha(entero_t *e); que
desplace el entero e una posición a la derecha. En esta y todas las funciones
se devuelve true en caso de éxito.
Corrimiento a izquierda
Implementar la función bool entero_desplazar_izquierda(entero_t *e);
que desplace el entero e una posición a la izquierda.
Notar que el vector puede necesitar crecer.
Suma
Implementar la función
bool entero_sumar(entero_t *a, const entero_t *b); que realice la
operación \(a = a + b\).
El algoritmo de la suma es el ya descripto, sumar componente a componente y de obtener un uno en el bit 33avo acarrear a la siguiente suma.
Resta
Implementar la función
bool entero_restar(entero_t *a, const entero_t *b); que realice la
operación \(a = a - b\). Como trabajamos con números positivos la resta
sólo se puede realizar si \(a > b\).
El algoritmo de la resta es similar al de la suma. Restar componente a componente. Si el 33avo bit vale uno (también valdrán uno el resto de los bits superiores, no importa por qué) entonces hay que acarrear a la siguiente resta. A diferencia del algoritmo de la suma, el acarreo es un uno que se resta en la siguiente operación.
Binario a BCD
Implementar la función
char *entero_a_bcd(const entero_t *entero, size_t *n) que realice la
conversión del entero en un número BCD utilizando el algoritmo de double
dabble. La función devolverá por el nombre el arreglo de dígitos BCD y por la
interfaz, a través de n la cantidad de dígitos empleados.
El algoritmo de double dabble nos dice que extendamos nuestro binario con bits
suficientes a izquierda para almacenar nuestros dígitos BCD. Nuestro número
mide b = entero->n * 32 bits, más o menos necesitamos 3,32 dígitos decimales
menos. Si vamos a utilizar 4 bits decimales por BCD entonces nos alcanza con
reservar \(b + 4 \lceil b / 3 \rceil\) bits adicionales a izquierda.
Luego de eso tenemos que repetir \(b\) veces:
Para cada dígito BCD, si es 5 o más de 5 sumarle 3.
Desplazar todo a la izquierda.
En los bits agregados quedarán los dígitos BCD.
Nota
Es válido tanto implementar el algoritmo trabajando sobre un entero_t,
extendiéndolo y sabiendo que todos los d por encima de n corresponden
cada uno a 8 dígitos BCD, esto sería una extensión del ejercicio resuelto
en clase.
También sería válido generar los dígitos BCD ya directamente en un arreglo
de char e implementar la operación de corrimiento para el paso 2. del
algoritmo.
Ambas opciones son igualmente válidas.
BCD a binario
Implementar la función
entero_t *entero_desde_bcd(const char bcd[], size_t n); que reciba un
número bcd de n dígitos y devuelva su representación como binario.
El algoritmo de double dabble es perfectamente reversible, se deja un espacio a derecha de una cantidad \(b\) de bits para el binario, luego se siguen los pasos:
Repetir \(b\) veces:
Desplazar a la derecha.
Para cada dígito BCD, si es 7 o mayor a 7 restarle 3.
En los \(b\) bits menos significativos quedará el binario.
En el artículo de Wikipedia hay un ejemplo de double dabble reverso: https://en.m.wikipedia.org/wiki/Double_dabble
Imprimir entero
Implementar la función bool entero_imprimir(const entero_t *entero);
que imprima el entero por stdout.
Nota
Convertir a BCD y utilizar la función de impresión de BCD del EJ1.
Aplicación
División
El algoritmo de división con restitución es el siguiente:
Se tiene un dividendo \(n\) y un divisor \(d\). El dividendo \(n\) tiene \(b\) bits.
Desplazamos \(d\) \(b\) veces a la izquierda.
Inicializamos \(r = n\) y \(q = 0\).
\(b\) veces:
Desplazamos \(q\) una vez a la izquierda.
Desplazamos \(r\) una vez a la izquierda.
Si \(r > d\):
Actualizamos \(r = r - d\).
Ponemos en 1 el bit menos significativo de \(q\).
Desplazamos \(r\) \(b\) veces a la derecha.
Después de estos pasos \(q = n / d\) y \(r = n \mod d\), el cociente y resto respectivamente.
Teniendo las funciones previamente programadas podemos implementar entonces la división como:
/*
Divide el dividendo por el divisor.
Devuelve el cociente por el nombre y el resto por la interfaz.
*/
entero_t *entero_dividir(const entero_t *dividendo, const entero_t *divisor, entero_t **resto) {
entero_t *d = entero_clonar(divisor);
entero_t *r = entero_clonar(dividendo);
entero_t *q = _crear(1);
if(d == NULL || r == NULL || q == NULL) {
entero_destruir(d);
entero_destruir(r);
entero_destruir(q);
return NULL;
}
// Podríamos tener una función para desplazar elementos en el arreglo.
for(size_t i = 0; i < dividendo->n * 32; i++)
entero_desplazar_izquierda(d);
for(size_t i = 0; i < dividendo->n * 32; i++) {
entero_desplazar_izquierda(q);
entero_desplazar_izquierda(r);
if(entero_comparar(r, d) >= 0) {
entero_restar(r, d);
q->d[0] |= 1;
}
}
entero_destruir(d);
// Podríamos tener una función para desplazar elementos en el arreglo.
for(size_t i = 0; i < dividendo->n * 32; i++)
entero_desplazar_derecha(r);
*resto = r;
return q;
}
Notar que si bien esta función no utiliza todas las operaciones aritméticas implementadas utiliza la mayoría.
Además vamos a programar una función auxiliar para poder ver el contenido de
la estructura que representa el entero_t:
void _imprimir(const entero_t *e, const char *pre, const char *post) {
printf("%s", pre);
for(size_t i = e->n; i > 0; i--)
printf(" %08x", e->d[i - 1]);
printf("%s", post);
}
Y vamos a agregar dentro de nuestra división las siguientes líneas al comienzo de la iteración principal de la función:
printf("Iteración %zd\n", i);
_imprimir(q, "\tq =", " ("); entero_imprimir(q); puts(")");
_imprimir(r, "\tr =", " ("); entero_imprimir(r); puts(")");
Para poder ver exactamente cuánto van valiendo q y r en cada paso.
La división de 1234567890 por 123 da como resultado 10037137 con resto 39.
Esta es la salida de nuestra función de división al ser llamada con esos valores (se agregaron un par de líneas de impresión):
Inicio
dividendo = 499602d2 (1_234_567_890)
divisor = 0000007b (123)
Antes de empezar el ciclo
d = 0000007b 00000000 (528_280_977_408)
Iteración 0
q = 00000000 (0)
r = 499602d2 (1_234_567_890)
Iteración 1
q = 00000000 (0)
r = 932c05a4 (2_469_135_780)
Iteración 2
q = 00000000 (0)
r = 00000001 26580b48 (4_938_271_560)
Iteración 3
q = 00000000 (0)
r = 00000002 4cb01690 (9_876_543_120)
Iteración 4
q = 00000000 (0)
r = 00000004 99602d20 (19_753_086_240)
Iteración 5
q = 00000000 (0)
r = 00000009 32c05a40 (39_506_172_480)
Iteración 6
q = 00000000 (0)
r = 00000012 6580b480 (79_012_344_960)
Iteración 7
q = 00000000 (0)
r = 00000024 cb016900 (158_024_689_920)
Iteración 8
q = 00000000 (0)
r = 00000049 9602d200 (316_049_379_840)
Iteración 9
q = 00000001 (1)
r = 00000018 2c05a400 (103_817_782_272)
Iteración 10
q = 00000002 (2)
r = 00000030 580b4800 (207_635_564_544)
Iteración 11
q = 00000004 (4)
r = 00000060 b0169000 (415_271_129_088)
Iteración 12
q = 00000009 (9)
r = 00000046 602d2000 (302_261_280_768)
Iteración 13
q = 00000013 (19)
r = 00000011 c05a4000 (76_241_584_128)
Iteración 14
q = 00000026 (38)
r = 00000023 80b48000 (152_483_168_256)
Iteración 15
q = 0000004c (76)
r = 00000047 01690000 (304_966_336_512)
Iteración 16
q = 00000099 (153)
r = 00000013 02d20000 (81_651_695_616)
Iteración 17
q = 00000132 (306)
r = 00000026 05a40000 (163_303_391_232)
Iteración 18
q = 00000264 (612)
r = 0000004c 0b480000 (326_606_782_464)
Iteración 19
q = 000004c9 (1_225)
r = 0000001d 16900000 (124_932_587_520)
Iteración 20
q = 00000992 (2_450)
r = 0000003a 2d200000 (249_865_175_040)
Iteración 21
q = 00001324 (4_900)
r = 00000074 5a400000 (499_730_350_080)
Iteración 22
q = 00002649 (9_801)
r = 0000006d b4800000 (471_179_722_752)
Iteración 23
q = 00004c93 (19_603)
r = 00000060 69000000 (414_078_468_096)
Iteración 24
q = 00009927 (39_207)
r = 00000045 d2000000 (299_875_958_784)
Iteración 25
q = 0001324f (78_415)
r = 00000010 a4000000 (71_470_940_160)
Iteración 26
q = 0002649e (156_830)
r = 00000021 48000000 (142_941_880_320)
Iteración 27
q = 0004c93c (313_660)
r = 00000042 90000000 (285_883_760_640)
Iteración 28
q = 00099279 (627_321)
r = 0000000a 20000000 (43_486_543_872)
Iteración 29
q = 001324f2 (1_254_642)
r = 00000014 40000000 (86_973_087_744)
Iteración 30
q = 002649e4 (2_509_284)
r = 00000028 80000000 (173_946_175_488)
Iteración 31
q = 004c93c8 (5_018_568)
r = 00000051 00000000 (347_892_350_976)
Al terminar el ciclo
q = 00992791 (10_037_137)
r = 00000027 00000000 (167_503_724_544)
Resultado
cociente = 00992791 (10_037_137)
resto = 00000027 (39)
Cada vez que \(r > d\) se entra al if, notar que esto pasa recién en la
iteración 8.
Programa
Implementar un programa que lea de stdin de a dos números por vez hasta
que el usuario dispare la señal de fin de archivo. El programa debe imprimir el
resultado de la división y el resto de la misma. Además debe imprimir la suma
entre ambos números.
Nota
En clase se implementó una función para leer un BCD de stdin, puede
utilizarse esa función.
Entrega
Deberá entregarse el código fuente del programa desarrollado.
El programa debe:
Compilar correctamente con los flags:
-Wall -Werror -std=c99 -pedantic
pasar Valgrind correctamente,
La entrega se realiza a través del sistema de entregas.
El ejercicio es de entrega individual.