¿Cómo ocurre la división dentro de las computadoras digitales? ¿Cuál es el algoritmo para ello?
He buscado mucho en google pero no he obtenido resultados satisfactorios. Proporcione un algoritmo / diagrama de flujo muy claro para el algoritmo de división con una ilustración de muestra.
computers
tutorial
arithmetic-division
programa-o-steve
fuente
fuente
Respuestas:
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 sugiero que lea sobre cómo funcionan la suma y resta binarias si aún no está familiarizado con estos conceptos.
División lenta
Los métodos lentos más simples funcionan de la siguiente manera: reste el denominador del numerador. Haga esto de forma recursiva con el resultado de cada resta hasta que el resto sea menor que el denominador. La cantidad de iteraciones es el cociente entero, y la cantidad restante es el resto.
Ejemplo:
7/3:
Por lo tanto, la respuesta es 2 con un resto de 1. Para hacer que esta respuesta sea un poco más relevante, aquí hay algunos antecedentes. La sustracción binaria mediante la suma del negativo se realiza, por ejemplo: 7 - 3 = 7 + (-3). Esto se logra utilizando el complemento de sus dos. Cada número binario se agrega usando una serie de sumadores completos:
Donde cada sumador completo de 1 bit se implementa de la siguiente manera:
División rápida
Si bien el método de división más lento es fácil de entender, requiere iteraciones repetitivas. Existen varios algoritmos "rápidos", pero todos se basan en la estimación.
Considere el método Goldschmidt:
Este método funciona de la siguiente manera:
Este método usa la multiplicación binaria mediante la suma iterativa, que también se usa en las CPU AMD modernas.
fuente
El hardware para la división de punto flotante es parte de una unidad lógica que también multiplica; Hay un módulo de hardware multiplicador disponible. Los números de coma flotante, digamos A y B, se dividen (formando A / B) por
Las mantisas (los dígitos binarios de los números) son un número binario de punto fijo entre 1/2 y 1; eso significa que el primer dígito después del punto binario es '1', seguido de ceros y unos ... como primer paso, una tabla de búsqueda encuentra el recíproco exacto a seis bits (solo hay 32 posibilidades, es una tabla pequeña)
Curiosamente, el viejo error de división Pentium (muy interesante en 1994) fue causado por un error de impresión que hizo que los valores de la tabla recíproca fueran incorrectos para el paso (4). Un artículo temprano, "Un método de división usando un multiplicador paralelo", Domenico Ferrari, IEEE Trans. Electrón. Comput EC-16 / 224-228 (1967), describe el método, al igual que "El Sistema IBM / 360 Modelo 91: Unidad de Ejecución de Punto Flotante" IBM J. Res. Dev. 11 : 34-53 (1967).
fuente
Existen métodos muy diferentes para la división, dependiendo de los números a manejar. Para enteros, el método shift-and-sustract dado por otros funcionará bien. Sin embargo, para los números de coma flotante, puede ser más rápido calcular primero el recíproco del denominador y luego multiplicarlo por su numerador.
El cálculo del recíproco del denominador no es tan malo; Se realiza mediante el refinamiento de aproximaciones sucesivas. Deje que g sea su suposición para 1 / d. Para una suposición mejorada, use g '= g (2-gd). Esto converge cuadráticamente, por lo que duplica los dígitos de precisión en cada mejora.
Ejemplo: calcular el recíproco de 3.5.
Su conjetura inicial es 0.3. Calcula 0.3 * 3.5 = 1.15. Su conjetura ajustada es 0.3 * (2 - 1.15) = 0.285. Ya muy cerca! Repita el proceso y obtendrá 0.2857125, y un tercer intento obtendrá 0.2857142857.
Hay algunos atajos. En coma flotante, puede extraer potencias de diez o potencias de dos, dependiendo de la base numérica de su máquina. Y, para la velocidad a expensas de un mayor uso de memoria, puede usar una tabla precalculada para números en el rango de 1 a b (donde b es su base de números) para obtener una suposición que esté inmediatamente cerca del recíproco requerido y guardar 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 alumno Anatoly Karatsuba, nunca se sabe cuándo se encontrará un método más rápido o mejor. Nunca rindas tu curiosidad.
fuente
Las computadoras no hacen una suma iterativa para multiplicar números, sería realmente lento. En cambio, hay algunos algoritmos de multiplicación rápida. Echa un vistazo: http://en.wikipedia.org/wiki/Karatsuba_algorithm
fuente