En artículos anteriores hemos visto las operaciones de suma y multiplicación de números enteros binarios. Veamos ahora la división, otra de las operaciones aritmética elementales que debe implementar un microprocesador.



Una división o cociente entre dos números enteros x / y, produce dos resultados Q (cociente) y R (resto) tales que:

x = y * Q + R

Donde el resto R está acotado por 0 <= R < y.

Cualquiera sea la base numérica, la división es prueba y error. El método de división que nos enseñaron en la escuela primaria es idéntico a lo que hace una unidad aritmético-lógica dentro de un microprocesador. Para cada dígito del cociente se debe encontrar un valor tal que, multiplicado por el divisor, la diferencia de restarlo al dividendo parcial se encuentre entre 0 y la base.

Veamos un ejemplo en decimal:

Empezando desde el dígito más significativo del dividendo, se busca un múltiplo (desde 1 hasta 9) del divisor tal que el resto se encuentre entre 0 y la base:

Se prueba con el menor múltiplo posible hasta que falle (el resto es negativo) y se obtiene el múltiplo (última prueba antes de fallar). Si no se encuentra un múltiplo, el dígito del cociente es cero y se avanza hacia posiciones menos significativas tanto del dividendo como del cociente (si falla en el inicio se trata de un cero a la izquierda, con lo cual no se representa).

La operación de comenzar con el dígito más significativo del dividendo y avanzar hacia posiciones menos significativas (marcando la posición del dividendo inicial con ' y bajando un nuevo dígito del dividendo en cada iteración) no es otra cosa que hacer shift a izquierda:

La operación continúa hasta llegar al dígito menos significativo del dividendo.

En la base binaria la operación es más simple, pues los bits del cociente pueden ser sólo 1 ó 0. Es decir se resta el divisor o no. El único múltiplo posible es 1 (trivial).

La ALU carga el dividendo en el registro MQ, el divisor en B e inicializa en ceros al registro A. Al igual que en la multiplicación, los registros A y MQ están conectados con capacidad de shift a izquierda y derecha.

En cada iteración se hace un shift a izquierda para avanzar al siguiente bit del dividendo y se resta el divisor. Si la resta es negativa, se deberá restaurar al valor anterior del dividendo parcial sumando el divisor (restoring) y el bit del cociente es 0. Si la resta es positiva, el nuevo dividendo parcial es correcto y el bit del cociente es 1.

En el primer shift ingresará un valor desconocido que se marca con guion y que será descartado en la última iteración (al ingresar el último bit del cociente).

Veamos un ejemplo:

En la última iteración se hace un shitf a izquierda sólo en el registro MQ (se desconecta de A) para que ingrese el bit menos significativo del cociente (q0) y al mismo tiempo se descarte el bit residual del comienzo.

Se observa que la operación es exactamente igual a la del algoritmo decimal que nos enseñaron en la escuela primaria, pero en base binaria. Sin embargo este algoritmo tiene una desventaja en cuanto a complejidad. Potencialmente puede requerir dos sumas por cada iteración (si el cociente es cero y siempre es necesario restaurar). Con operandos de n bits en el peor caso se harán 2n sumas.

Un método superador al algoritmo de división con restauración es el algoritmo de división sin restauración (sin restoring). Cuando el resto es negativo, en lugar de restaurar deja el dividendo parcial tal como está y cambia el signo del divisor. Es decir, si "nos pasamos" y el resto queda negativo, se deja como está y en la siguiente iteración se sumará el divisor en lugar de restar. Como siempre, mientras el resto de negativo el qi será cero.

Si en la última iteración el resto queda negativo significa que nos pasamos (falló la última prueba) y se debe corregir sumando el divisor.

Veamos el mismo ejemplo, ahora sin restoring:

Tal como se observa, la cantidad de sumas realizadas por este algoritmo baja de 2n a n+1, con lo cual resulta mucho más eficiente en cuanto a tiempo de cómputo.

Referencias


Tal vez pueda interesarte


Compartí este artículo