¿Cómo ocurre la división en nuestras computadoras?

Los algoritmos de división en diseños digitales se pueden dividir en dos categorías principales. División lenta y división rápida.

Le sugeriría que lea cómo funcionan las sumas y restas binarias si aún no está familiarizado con estos conceptos.

División lenta

Los métodos lentos más simples funcionan básicamente de la siguiente manera. Tome el número a dividir (numerador o dividendo) y reste el divisor de él. Haga esto recursivamente con el resultado de cada resta hasta que el resto sea menor que el divisor. Esta cantidad restante es el resto. La cantidad de iteraciones es el cociente.

Ejemplo:

7/3:

1. $$ 7-3 = 4 $$
2. $$ 4-3 = 1 $$
3. $$ 1 < 3 $$

Por lo tanto, la respuesta es 2 resto 1. Para que esta respuesta sea un poco más relevante, aquí hay algunos antecedentes. La resta binaria se realiza mediante la adición del negativo, por ejemplo: 7 - 3 = 7 + (-3). Esto se logra mediante el uso de dos números binarios complementarios. Cada número binario se agrega mediante una serie de sumadores completos:

Dondecadasumadorde1bitseimplementadelasiguientemanera:

División rápida

Si bien la división lenta es fácil de entender, requiere repeticiones repetitivas. Existen varios algoritmos "rápidos", pero todos dependen de la estimación.

Considere el método Goldschmidt:

Haré uso de lo siguiente: $$ Q = \ frac {N} {D} $$

Este método funciona de la siguiente manera:

1. Multiplicar N y D con una fracción F es tal que D se acercó a 1.
2. A medida que D se acerca a 1, N se acerca a Q

Este método utiliza la multiplicación binaria que se realiza mediante la suma iterativa. También se usa en las modernas CPU de AMD.

Existen diferentes métodos de división, según los números que se manejarán. Para los enteros, el método de cambio y resta dado por otros funcionará bien. Sin embargo, para los números de punto flotante, puede ser más rápido calcular primero el recíproco del denominador y luego multiplicar eso por su numerador.

El cálculo del recíproco del denominador no es tan malo; Se hace refinando aproximaciones sucesivas. Dejemos que g sea tu conjetura para 1 / d. Para una estimación mejorada, use g '= g (2-gd). Esto converge cuadráticamente, por lo que dobla los dígitos de precisión en cada mejora.

Ejemplo: calcular el recíproco de 3.5.

Tu estimación inicial es 0.3. Calculas 0.3 * 3.5 = 1.15. Su estimación ajustada es 0.3 * (2 - 1.15) = 0.285. ¡Ya está bastante cerca! Repita el proceso y obtendrá 0.2857125, y un tercer intento obtiene 0.2857142857.

Hay algunos atajos. En punto flotante, puede extraer potencias de diez o potencias de dos, según la base numérica de su máquina. Y, para la velocidad a expensas de un mayor uso de la memoria, puede usar una tabla precalculada para los números en el rango de 1 a b (donde b es su base numérica) para obtener una estimación que se encuentre inmediatamente cerca del recíproco requerido y guarda uno o dos pasos de refinamiento.

Tenga en cuenta que, al igual que con la multiplicación y la vergüenza de Kolmogorov en 1960 por su estudiante Anatoly Karatsuba, nunca se sabe cuándo se encontrará un método más rápido o mejor. Nunca renuncies a tu curiosidad.

Las computadoras no hacen una adición iterativa para multiplicar números, sería muy lento. En cambio, hay algunos algoritmos de multiplicación rápida. Revisa: enlace