La división de enteros en el hardware de la computadora se realiza mediante la sustracción y el desplazamiento de los dígitos exactamente como la división de mano larga típica en el método más crudo, mientras que los mejores métodos utilizan algoritmos que calculan el resultado mucho más rápido y en menos pasos.
Hablaré sobre los métodos de división lenta. Restaurar y no restaurar la división de enteros, que se basan en la división básica a mano, sin embargo, existen algoritmos más eficientes utilizados para la división rápida como la división de Newton-Raphson y la división de Goldschmidt.
División de restauración:
- ¿Paytm es el lugar adecuado para comprar una computadora portátil?
- ¿Cómo los humanos permitieron que las máquinas entendieran el código de máquina?
- ¿Es importante una alta cobertura sRGB al elegir una computadora portátil para animación y modelado?
- ¿Qué características debe buscar un maníaco de un producto Adobe (es decir, Photoshop, Illustator, After Effects, etc.) en una computadora portátil?
- ¿Qué CPU se recomienda para jugar juegos exigentes a 1080p y ver videos HD al mismo tiempo?
Disposición de circuito para división binaria
(No necesita este diagrama de aspecto aterrador para comprender cómo funciona, pero una vez que lo haga, tendrá mucho más sentido).
Un divisor positivo de n bits se carga en el registro M y un dividendo positivo de n bits se carga en el registro Q al principio. El registro A se establece en 0, es decir, todos sus flip flops tienen el valor 0.
Tenga en cuenta que un registro es solo un grupo de flip flops, y un flip flop es solo un elemento de almacenamiento que puede contener 0 o 1.
Por lo tanto, un registro que consta de ocho flip flops puede contener una serie de ocho dígitos, cada uno de los cuales es 0 o 1-, por ejemplo 00100100.
Al final de la división, el cociente de n bits estará en el registro Q con el resto en el registro A.
Entonces, básicamente, si tomáramos el ejemplo,
13/3 = 4, con un resto de 1.
El registro Q inicialmente tendría un valor de 13.
El registro M tendría un valor de 3.
Y el registro A tendría un valor de 0 (al principio).
Al final de la división, el registro A (resto) tendría un valor de 1 y el registro Q (cociente) tendría un valor de 4.
Convirtiendo todo esto en binario se convertiría en
1101/11 = 100, con un resto de 1.
El registro Q inicialmente tendría un valor de 1101.
El registro M tendría un valor de 11.
Y el registro A tendría un valor de 0 (al principio).
Al final de la división, el registro A (resto) tendría un valor de 1 y el registro Q (cociente) tendría un valor de 100.
Por lo tanto, tome la típica división a mano alzada del mismo ejemplo:
11) 1101 (100
-11
—–
00
-11
——
x (demasiado pequeño)
——
——> 001
– 11
———
X
_______
—-> 001 (resto)
El mismo procedimiento (que a pesar de las apariencias es exactamente el mismo procedimiento que la división de manos largas) se refleja a través de registros en este algoritmo:
- El cambio A y Q dejó una posición binaria.
- Resta M de A y coloca la respuesta de nuevo en A.
- Si el signo de A es 1, establezca q en 0 y agregue M nuevamente a A (es decir, restaure A); de lo contrario, establezca Q en 1 (Aquí q es la posición vacante más a la derecha a la izquierda después de que todos los valores de Q se desplacen un bit a la izquierda).
Como se muestra en la figura, los registros A y Q se sientan uno al lado del otro, o podrían ser las dos partes de un registro más grande.
El registro Q tiene 4 bits para esta división de un entero de 4 bits, pero el registro A tiene 5 para dar cuenta del préstamo.
La resta se realiza mediante el método del complemento a 2.
Aquí está el algoritmo de división, que se muestra a través del contenido de los registros en cada paso:
(reg A) (reg Q) El registro A contiene 00000 mientras que Q contiene 1101
0 0 0 0 0 1 1 0 1 Inicialmente, valores de A y Dividendo Q
0 0 0 1 1 Divisor M
0 0 0 0 1 1 0 1 _ A y Q se desplazaron a la izquierda
+
1 1 1 0 1. Equivalente a -11 (complemento de 2 de 11)
________
[1] 1 1 1 0 Como el resultado de 1 – 11 es negativo, restaure
+
1 1 agregando 11 de vuelta
________
0 0 0 0 1 1 0 1 [0] Como el valor en el cuadro de arriba es 1, el valor en
_______________ el cuadro de la derecha q es 0. Se restaura el valor de 1
0 0 0 1 1 0 1 [0] _ Ahora A y Q se desplazan nuevamente, dejando un espacio en blanco.
+
1 1 1 0 1
________
[0] 0 0 0 0 Como la diferencia no es negativa, no se requiere restauración.
0 1 [0] [1] Como el valor en el cuadro es 0, el valor de q es 1
_______
0 0 0 0 0 1 [0] [1] _ Shift, una vez más.
+
1 1 1 0 1 Resta 11, nuevamente
_______
[1] 1 1 0 1 Negativo, así que restaure.
+
1 1
________
0 0 0 0 0 1 [0] [1] [0] q es 0, porque el cuadro anterior tenía 1.
0 0 0 0 1 [0] [1] [0] _ Shift, una última vez.
+
1 1 1 0 1 Restar 11
_________
[1] 1 1 1 0. Como es negativo, restaure.
+
1 1
________
0 0 0 0 1 [0] [1] [0] [0] Como el valor en el cuadro de arriba es 1, q es 0.
_________ _________
Reg A Reg Q
Aleta.
Y ahora, después de cuatro iteraciones del proceso para los cuatro bits, hemos terminado.
El registro A contiene el resto A 1, y el registro Q contiene el cociente 100.
Ahora, si desea saber cómo se podría ajustar esto para hacerlo más eficiente y menos lento con menos pasos, presento:
División no restauradora:
Esto es exactamente lo mismo que antes, excepto cuando la diferencia entre la parte del dividendo y el divisor resulta ser negativa, no se restaura de nuevo y luego se desplaza hacia la izquierda, simplemente se desplaza directamente y se restablece el desplazamiento valor en su lugar!
Aquí está el algoritmo:
Paso 1: haz lo siguiente n veces
- Si el signo de A es 0, cambie A y Q a la izquierda una posición de bit y reste M de A; de lo contrario, mueva A y Q hacia la izquierda y agregue M a A.
- Ahora, si el signo de A es 0, establezca q en 1; de lo contrario, establezca q en 0.
Paso 2: si el signo de A es 1, agregue M a A.
Aquí vamos de nuevo-
(reg A) (reg Q)
0 0 0 0 0 1 1 0 1 Inicialmente, A y Dividendo Q
0 0 0 1 1 Divisor M
0 0 0 0 1 1 0 1 _ A y Q se desplazaron a la izquierda
+
1 1 1 0 1 Restar 11
__________
[1] 1 1 1 0 1 0 1 [0] Establezca q en 0, aquí mismo. Ahora, aunque sea
negativo,
1 1 1 0 1 0 1 [0] _ no restaurar, solo cambiar.
+
1 1 Agregue 11 de nuevo ahora.
________
[0] 0 0 0 0 0 1 [0] [1] Como el cuadro tiene 0, q es 1.
0 0 0 0 0 1 [0] [1] _ Ahora, solo cambia directamente de nuevo.
+
1 1 1 0 1 Ahora, como la diferencia anterior fue positiva, reste 11
_________
[1] 1 1 0 1 1 [0] [1] [0] Como el valor en el cuadro es 1, q es igual a 0.
1 1 0 1 1 [0] [1] [0] _ Shift, nuevamente.
+
1 1 Restaurar el nuevo valor.
_________
[1] 1 1 1 0 [0] [1] [0] [0] Como el valor en el cuadro es 1, q es 0.
+
1 1 Como es negativo, restaure (Paso 2).
__________
0 0 0 0 1 [0] [1] [0] [0]
_________ ____________
Registrarse A Registrarse Q
Aleta.
Entonces, tenemos el mismo valor de 1 como resto en el registro A y 100 como cociente en el registro Q, de una manera mucho más eficiente.
_______________________________________________________
¡Eso es todo amigos!
Gracias por leer.