Un algoritmo de división es un algoritmo que, dados dos números enteros N y D, calcula su cociente y / o resto , el resultado de la división euclidiana . Algunos se aplican a mano, mientras que otros se emplean mediante software y diseños de circuitos digitales.
Los algoritmos de división se dividen en dos categorías principales: división lenta y división rápida. Los algoritmos de división lenta producen un dígito del cociente final por iteración. Los ejemplos de división lenta incluyen restauración , restauración no satisfactoria, no restauración y división SRT . Los métodos de división rápida comienzan con una aproximación cercana al cociente final y producen el doble de dígitos del cociente final en cada iteración. Los algoritmos de Newton-Raphson y Goldschmidt entran en esta categoría.
Las variantes de estos algoritmos permiten utilizar algoritmos de multiplicación rápida . Resulta que, para números enteros grandes, el tiempo de computadora necesario para una división es el mismo, hasta un factor constante, que el tiempo necesario para una multiplicación, cualquiera que sea el algoritmo de multiplicación que se utilice.
La discusión se referirá al formulario , dónde
- N = numerador (dividendo)
- D = denominador (divisor)
es la entrada, y
- Q = cociente
- R = resto
es la salida.
División por resta repetida
El algoritmo de división más simple, históricamente incorporado en un algoritmo de máximo común divisor presentado en Elementos de Euclides , Libro VII, Proposición 1, encuentra el resto dados dos números enteros positivos usando solo restas y comparaciones:
R : = N mientras que R ≥ D haz R : = R - D end return R
La prueba de que el cociente y el resto existen y son únicos (descrita en la división euclidiana ) da lugar a un algoritmo de división completo que utiliza sumas, restas y comparaciones:
función dividir ( N , D ) si D = 0 entonces error ( DivisionByZero ) end si D < 0 entonces ( Q , R ) : = dividir ( N , - D ); return ( - Q , R ) end if N < 0 then ( Q , R ) : = divide ( - N , D ) if R = 0 then return ( - Q , 0 ) else return ( - Q - 1 , D - R ) end end - En este punto, N ≥ 0 y D> 0 devuelven divide_unsigned ( N , D ) end function divide_unsigned ( N , D ) Q : = 0 ; R : = N mientras R ≥ D hacer Q : = Q + 1 R : = R - D end return ( Q , R ) end
Este procedimiento siempre produce R ≥ 0. Aunque es muy simple, toma pasos de Ω (Q), por lo que es exponencialmente más lento que incluso los algoritmos de división lenta como la división larga. Es útil si se sabe que Q es pequeño (es un algoritmo sensible a la salida ) y puede servir como una especificación ejecutable.
División larga
La división larga es el algoritmo estándar que se utiliza para la división con lápiz y papel de números de varios dígitos expresados en notación decimal. Se desplaza gradualmente del extremo izquierdo al derecho del dividendo, restando el mayor múltiplo posible del divisor (a nivel de dígitos) en cada etapa; los múltiplos se convierten en los dígitos del cociente y la diferencia final es el resto.
Cuando se usa con una base binaria, este método forma la base para la división de enteros (sin signo) con el algoritmo de resto a continuación. La división corta es una forma abreviada de división larga adecuada para divisores de un dígito. Chunking , también conocido como método de cocientes parciales o método del ahorcado, es una forma menos eficiente de división larga que puede ser más fácil de entender. Al permitir que uno reste más múltiplos de los que tiene actualmente en cada etapa, también se puede desarrollar una variante más libre de división larga [1]
División entera (sin firmar) con resto
El siguiente algoritmo, la versión binaria del famoso división larga , dividirá N por D , colocando el cociente en Q y el resto en R . En el siguiente código, todos los valores se tratan como enteros sin signo.
si D = 0 entonces el error ( DivisionByZeroException ) finaliza Q : = 0 - Inicializa el cociente y el resto a cero R : = 0 para i : = n - 1 .. 0 do - Donde n es el número de bits en N R : = R << 1 - Desplazamiento a la izquierda R en 1 bit R ( 0 ) : = N ( i ) - Establezca el bit menos significativo de R igual al bit i del numerador si R ≥ D entonces R : = R - D Q ( i ) : = 1 extremo extremo
Ejemplo
Si tomamos N = 1100 2 (12 10 ) y D = 100 2 (4 10 )
Paso 1 : Establezca R = 0 y Q = 0
Paso 2 : Tome i = 3 (uno menos que el número de bits en N)
Paso 3 : R = 00 (desplazado a la izquierda en 1)
Paso 4 : R = 01 (ajuste R (0) a N (i))
Paso 5 : R
Paso 2 : Establecer i = 2
Paso 3 : R = 010
Paso 4 : R = 011
Paso 5 : R
Paso 2 : Establecer i = 1
Paso 3 : R = 0110
Paso 4 : R = 0110
Paso 5 : R> = D, declaración ingresada
Paso 5b : R = 10 (R − D)
Paso 5c : Q = 10 (configuración Q ( i) a 1)
Paso 2 : Establecer i = 0
Paso 3 : R = 100
Paso 4 : R = 100
Paso 5 : R> = D, declaración ingresada
Paso 5b : R = 0 (R − D)
Paso 5c : Q = 11 (configuración Q ( i) a 1)
final
Q = 11 2 (3 10 ) y R = 0.
Métodos de división lenta
Todos los métodos de división lenta se basan en una ecuación de recurrencia estándar [2]
- ,
dónde:
- R j es el j -ésimo resto parcial de la división
- B es la raíz (base, generalmente 2 internamente en computadoras y calculadoras)
- q n - ( j + 1) es el dígito del cociente en la posición n− (j + 1) , donde las posiciones de los dígitos se numeran desde el menos significativo 0 hasta el más significativo n −1
- n es el número de dígitos en el cociente
- D es el divisor
Restaurando la división
La restauración de la división opera en números fraccionarios de coma fija y depende del supuesto 0 < D < N . [ cita requerida ]
Los dígitos del cociente q se forman a partir del conjunto de dígitos {0,1}.
El algoritmo básico para restaurar la división binaria (base 2) es:
R : = N D : = D << n - R y D necesitan el doble del ancho de palabra de N y Q para i : = n - 1 .. 0 do - Por ejemplo 31..0 para 32 bits R : = 2 * R - D - Resta de prueba del valor cambiado (la multiplicación por 2 es un cambio en la representación binaria) si R ≥ 0 entonces q ( i ) : = 1 - Resultado-bit 1 en caso contrario q ( i ) : = 0 - - Resultado-bit 0 R : = R + D - El nuevo resto parcial es (restaurado) valor desplazado fin fin- Donde: N = numerador, D = denominador, n = # bits, R = resto parcial, q (i) = bit #i del cociente
La división de restauración no efectiva es similar a la división de restauración, excepto que se guarda el valor de 2R, por lo que no es necesario volver a agregar D para el caso de R <0.
División no restauradora
La división sin restauración utiliza el conjunto de dígitos {−1, 1} para los dígitos del cociente en lugar de {0, 1}. El algoritmo es más complejo, pero cuando se implementa en hardware tiene la ventaja de que solo hay una decisión y una suma / resta por bit de cociente; no hay ningún paso de restauración después de la resta, lo que potencialmente reduce el número de operaciones hasta la mitad y permite que se ejecute más rápido. [3] El algoritmo básico para la división binaria (base 2) sin restauración de números no negativos es:
R : = N D : = D << n - R y D necesitan el doble del ancho de palabra de N y Q para i = n - 1 .. 0 sí - por ejemplo 31..0 para 32 bits si R > = 0 entonces q [ i ] : = + 1 R : = 2 * R - D si no q [ i ] : = - 1 R : = 2 * R + D end if end - Nota: N = numerador, D = denominador, n = # bits, R = resto parcial, q (i) = bit #i del cociente.
Siguiendo este algoritmo, el cociente está en una forma no estándar que consta de dígitos de -1 y +1. Esta forma debe convertirse a binaria para formar el cociente final. Ejemplo:
Convierta el siguiente cociente al conjunto de dígitos {0,1}: | |
Comienzo: | |
1. Forme el término positivo: | |
2. Enmascare el término negativo *: | |
3. Restar: : | |
*. (Notación binaria firmada con complemento a uno sin complemento a dos ) |
Si los −1 dígitos de se almacenan como ceros (0) como es común, entonces es y computación es trivial: realiza un complemento a uno (complemento bit a bit) en el original .
Q : = Q - bit . bnot ( Q ) * Apropiado si - 1 dígito en Q se representa como ceros como es común .
Finalmente, los cocientes calculados por este algoritmo son siempre impares, y el resto en R está en el rango −D ≤ R
si R < 0 entonces Q : = Q - 1 R : = R + D - Necesario solo si el resto es de interés. terminar si
El resto real es R >> n. (Al igual que con la restauración de la división, los bits de orden inferior de R se utilizan al mismo ritmo que se producen los bits del cociente Q, y es común utilizar un solo registro de desplazamiento para ambos).
División SRT
Llamada así por sus creadores (Sweeney, Robertson y Tocher), la división SRT es un método popular para la división en muchas implementaciones de microprocesadores . [4] [5] La división SRT es similar a la división sin restaurar, pero usa una tabla de búsqueda basada en el dividendo y el divisor para determinar cada dígito del cociente.
La diferencia más significativa es que se utiliza una representación redundante para el cociente. Por ejemplo, al implementar la división radix-4 SRT, cada dígito del cociente se elige entre cinco posibilidades: {−2, −1, 0, +1, +2}. Debido a esto, la elección de un dígito cociente no necesita ser perfecta; los dígitos posteriores del cociente pueden corregir errores leves. (Por ejemplo, los pares de dígitos del cociente (0, +2) y (1, −2) son equivalentes, ya que 0 × 4 + 2 = 1 × 4−2.) Esta tolerancia permite seleccionar los dígitos del cociente utilizando solo unos pocos bits más significativos del dividendo y el divisor, en lugar de requerir una resta de ancho completo. Esta simplificación, a su vez, permite utilizar una base superior a 2.
Al igual que la división sin restaurar, los pasos finales son una resta final de ancho completo para resolver el último bit del cociente y la conversión del cociente a la forma binaria estándar.
El infame error de división de punto flotante del procesador Intel Pentium fue causado por una tabla de búsqueda codificada incorrectamente. Cinco de las 1066 entradas se habían omitido por error. [6] [7]
Métodos de división rápida
División de Newton-Raphson
Newton-Raphson usa el método de Newton para encontrar el recíproco de y multiplica ese recíproco por para encontrar el cociente final.
Los pasos de la división Newton-Raphson son:
- Calcule una estimación por el recíproco del divisor .
- Calcule estimaciones sucesivamente más precisas de lo recíproco. Aquí es donde se emplea el método de Newton-Raphson como tal.
- Calcula el cociente multiplicando el dividendo por el recíproco del divisor: .
Para aplicar el método de Newton para encontrar el recíproco de , es necesario encontrar una función que tiene un cero en . La obvia tal función es, pero la iteración de Newton-Raphson para esto no es útil, ya que no se puede calcular sin conocer el recíproco de (además, intenta calcular el recíproco exacto en un paso, en lugar de permitir mejoras iterativas). Una función que funciona es, para lo cual la iteración de Newton-Raphson da
que se puede calcular a partir de usando sólo multiplicación y resta, o usando dos multiplicaciones- sumas fusionadas .
Desde un punto de vista de cálculo, las expresiones y no son equivalentes. Para obtener un resultado con una precisión de 2 n bits mientras se utiliza la segunda expresión, se debe calcular el producto entre y con el doble de la precisión dada de ( n bits). [ cita requerida ] Por el contrario, el producto entre y sólo necesitan calcularse con una precisión de n bits, porque los n bits iniciales (después del punto binario) de son ceros.
Si el error se define como , luego:
Esta cuadratura del error en cada paso de la iteración, la llamada convergencia cuadrática del método de Newton-Raphson, tiene el efecto de que el número de dígitos correctos en el resultado se duplica aproximadamente para cada iteración , una propiedad que se vuelve extremadamente valiosa cuando los números involucrados tienen muchos dígitos (por ejemplo, en el dominio de números enteros grandes). Pero también significa que la convergencia inicial del método puede ser comparativamente lenta, especialmente si la estimación inicial está mal elegido.
Para el subproblema de elegir una estimación inicial , es conveniente aplicar un desplazamiento de bits al divisor D para escalarlo de modo que 0.5 ≤ D ≤ 1; aplicando el mismo desplazamiento de bits al numerador N , se asegura que el cociente no cambia. Entonces se podría usar una aproximación lineal en la forma
para inicializar Newton-Raphson. Minimizar el máximo del valor absoluto del error de esta aproximación en el intervalo, uno debería usar
Los coeficientes de la aproximación lineal se determinan como sigue. El valor absoluto del error es. El mínimo del valor absoluto máximo del error está determinado por el teorema de equioscilación de Chebyshev aplicado a. El mínimo local de ocurre cuando , que tiene solución . La función en ese mínimo debe ser de signo opuesto a la función en los puntos finales, es decir,. Las dos ecuaciones en las dos incógnitas tienen una solución única y , y el error máximo es . Usando esta aproximación, el valor absoluto del error del valor inicial es menor que
Es posible generar un ajuste polinómico de grado mayor que 1, calculando los coeficientes usando el algoritmo de Remez . La compensación es que la conjetura inicial requiere más ciclos computacionales pero, con suerte, a cambio de menos iteraciones de Newton-Raphson.
Dado que para este método la convergencia es exactamente cuadrática, se deduce que
pasos son suficientes para calcular el valor hasta lugares binarios. Esto se evalúa como 3 para IEEE de precisión simple y 4 para formatos de doble precisión y doble extendido .
Pseudocódigo
Lo siguiente calcula el cociente de N y D con una precisión de P lugares binarios:
Exprese D como M × 2 e donde 1 ≤ M <2 (representación de coma flotante estándar)D ': = D / 2 e + 1 // escala entre 0,5 y 1, se puede realizar con desplazamiento de bits / resta de exponente
N': = N / 2 e + 1
X: = 48/17 - 32/17 × D ' // precalcular constantes con la misma precisión que D repetir veces // se puede calcular previamente basándose en P fijo X: = X + X × (1 - D '× X)fin volver N '× X
Por ejemplo, para una división de punto flotante de doble precisión, este método utiliza 10 multiplica, 9 suma y 2 desplazamientos.
Variante de la división de Newton-Raphson
El método de división de Newton-Raphson se puede modificar para que sea un poco más rápido de la siguiente manera. Después de cambiar N y D para que D esté en [0.5, 1.0], inicialice con
Este es el mejor ajuste cuadrático a 1 / D y da un valor absoluto del error menor o igual a 1/99. Se elige para igualar el error a un polinomio de Chebyshev de tercer orden reescalado del primer tipo. Los coeficientes deben calcularse previamente y codificarse de forma rígida.
Luego, en el ciclo, use una iteración que cubra el error.
El término Y · E es nuevo.
Si el bucle se realiza hasta que X esté de acuerdo con 1 / D en sus P bits iniciales, entonces el número de iteraciones no será superior a
que es el número de veces que se debe multiplicar 99 al cubo para llegar a 2 P +1 . Luego
es el cociente con P bits.
El uso de polinomios de mayor grado en la inicialización o la iteración da como resultado una degradación del rendimiento porque las multiplicaciones adicionales requeridas se gastarían mejor en hacer más iteraciones.
División Goldschmidt
La división Goldschmidt [8] (según Robert Elliott Goldschmidt [9] ) utiliza un proceso iterativo de multiplicar repetidamente tanto el dividendo como el divisor por un factor común F i , elegido de modo que el divisor converja a 1. Esto hace que el dividendo converja a la cociente buscado Q :
Los pasos para la división Goldschmidt son:
- Genere una estimación para el factor de multiplicación F i .
- Multiplica el dividendo y el divisor por F i .
- Si el divisor está lo suficientemente cerca de 1, devuelva el dividendo; de lo contrario, continúe con el paso 1.
Suponiendo que N / D se ha escalado de modo que 0 < D <1, cada F i se basa en D :
Al multiplicar el dividendo y el divisor por el factor se obtiene:
Después de un número suficiente k de iteraciones.
El método Goldschmidt se utiliza en CPU AMD Athlon y modelos posteriores. [10] [11] También se conoce como algoritmo de Anderson Earle Goldschmidt Powers (AEGP) y es implementado por varios procesadores de IBM. [12] [13]
Teorema del binomio
El método de Goldschmidt se puede utilizar con factores que permitan simplificaciones mediante el teorema del binomio . Suponga que N / D ha sido escalado por una potencia de dos tal que. Nosotros elegimos y . Esto produce
- .
Después pasos , el denominador se puede redondear a con un error relativo
que es máximo en Cuándo , proporcionando así una precisión mínima de dígitos binarios.
Métodos de números enteros grandes
Los métodos diseñados para la implementación de hardware generalmente no se escalan a números enteros con miles o millones de dígitos decimales; estos ocurren con frecuencia, por ejemplo, en reducciones modulares en criptografía . Para estos números enteros grandes, los algoritmos de división más eficientes transforman el problema para usar una pequeña cantidad de multiplicaciones, que luego se pueden hacer usando un algoritmo de multiplicación asintóticamente eficiente como el algoritmo de Karatsuba , la multiplicación de Toom-Cook o el algoritmo de Schönhage-Strassen . El resultado es que la complejidad computacional de la división es del mismo orden (hasta una constante multiplicativa) que la de la multiplicación. Los ejemplos incluyen la reducción a multiplicación por el método de Newton como se describe anteriormente , [14] así como la reducción de Barrett ligeramente más rápida y los algoritmos de reducción de Montgomery . [15] [ verificación necesaria ] El método de Newton es particularmente eficiente en escenarios donde uno debe dividir por el mismo divisor muchas veces, ya que después de la inversión inicial de Newton sólo se necesita una multiplicación (truncada) para cada división.
División por una constante
La división por una constante D es equivalente a la multiplicación por su recíproco . Dado que el denominador es constante, también lo es su recíproco (1 / D ). Así, es posible calcular el valor de (1 / D ) una vez en tiempo de compilación, y en tiempo de ejecución realizar la multiplicación N · (1 / D ) en lugar de la división de N / D . En aritmética de punto flotante, el uso de (1 / D ) presenta un pequeño problema, pero en aritmética de enteros, el recíproco siempre evaluará a cero (asumiendo | D |> 1).
No es necesario utilizar específicamente (1 / D ); se puede utilizar cualquier valor ( X / Y ) que se reduzca a (1 / D ). Por ejemplo, para la división por 3, se podrían usar los factores 1/3, 2/6, 3/9 o 194/582. En consecuencia, si Y fuera una potencia de dos, el paso de división se reduciría a un rápido desplazamiento de bits a la derecha. El efecto de calcular N / D como ( N · X ) / Y reemplaza una división con una multiplicación y un desplazamiento. Tenga en cuenta que los paréntesis son importantes, ya que N · ( X / Y ) evaluará a cero.
Sin embargo, a menos que D sea una potencia de dos, no hay X e Y que satisfaga las condiciones anteriores. Afortunadamente, ( N · X ) / Y da exactamente el mismo resultado que N / D en aritmética de enteros incluso cuando ( X / Y ) no es exactamente igual a 1 / D , pero "lo suficientemente cerca" que el error introducido por la aproximación es en los bits que son descartados por la operación de cambio. [16] [17] [18]
Como ejemplo aritmético concreto de coma fija , para enteros sin signo de 32 bits, la división por 3 se puede reemplazar con una multiplicación por2863311531/2 33, una multiplicación por 2863311531 ( hexadecimal 0xAAAAAAAB) seguida de un desplazamiento de 33 bits a la derecha. El valor de 2863311531 se calcula como 2 33/3, luego redondeado.
Asimismo, la división por 10 se puede expresar como una multiplicación por 3435973837 (0xCCCCCCCD) seguida de una división por 2 35 (o desplazamiento de 35 bits a la derecha).
En algunos casos, la división por una constante se puede lograr en incluso menos tiempo al convertir "multiplicar por una constante" en una serie de cambios y sumas o restas . [19] De particular interés es la división por 10, para lo cual se obtiene el cociente exacto, con el resto si es necesario. [20]
Error de redondeo
Las operaciones de división pueden introducir errores de redondeo debido a la precisión limitada .
Ver también
- División de galeras
- Algoritmo de multiplicación
- Error de Pentium FDIV
Referencias
- ^ "La guía definitiva de matemáticas superiores a la división larga y sus variantes - para enteros" . Bóveda de matemáticas . 2019-02-24 . Consultado el 24 de junio de 2019 .
- ^ Morris, James E .; Iniewski, Krzysztof (22 de noviembre de 2017). Manual de aplicaciones de dispositivos nanoelectrónicos . Prensa CRC. ISBN 978-1-351-83197-0.
- ^ Flynn. "Stanford EE486 (División aritmética informática avanzada) - Folleto del capítulo 5 (División)" (PDF) . Universidad de Stanford .
- ^ Harris, David L .; Oberman, Stuart F .; Horowitz, Mark A. (9 de septiembre de 1998). División SRT: Arquitecturas, Modelos e Implementaciones (PDF) (Informe técnico). Universidad Stanford.
- ^ McCann, Mark; Pippenger, Nicholas (2005). "Algoritmos de división SRT como sistemas dinámicos" . Revista SIAM de Computación . 34 (6): 1279–1301. CiteSeerX 10.1.1.72.6993 . doi : 10.1137 / S009753970444106X .
- ^ "Análisis estadístico de defecto de punto flotante" . Corporación Intel. 1994 . Consultado el 22 de octubre de 2013 .
- ^ Oberman, Stuart F .; Flynn, Michael J. (julio de 1995). Un análisis de implementaciones y algoritmos de división (PDF) (Informe técnico). Universidad Stanford. CSL-TR-95-675.
- ^ Goldschmidt, Robert E. (1964). Aplicaciones de la división por convergencia (PDF) (Tesis). M.Sc. disertación. MIT OCLC 34136725 .
- ^ https://web.archive.org/web/20180718114413/https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5392026
- ^ Oberman, Stuart F. (1999). "División de punto flotante y algoritmos de raíz cuadrada e implementación en el microprocesador AMD-K7" (PDF) . Actas del Simposio de IEEE sobre aritmética informática : 106-115. doi : 10.1109 / ARITH.1999.762835 . S2CID 12793819 .
- ^ Soderquist, Peter; Leeser, Miriam (julio-agosto de 1997). "División y raíz cuadrada: elegir la implementación correcta" . IEEE Micro . 17 (4): 56–66. doi : 10.1109 / 40.612224 .
- ^ SF Anderson, JG Earle, RE Goldschmidt, DM Powers. IBM 360/370 modelo 91: unidad de ejecución de punto flotante , IBM Journal of Research and Development , enero de 1997
- ^ Chico incluso, Peter-M. Seidel, Warren E. Ferguson. Un análisis de error paramétrico del algoritmo de división de Goldschmidt . 2004, [1]
- ^ Hasselström, Karl (2003). División rápida de números enteros grandes: una comparación de algoritmos (PDF) (Tesis de Maestría en Ciencias de la Computación). Real Instituto de Tecnología. Archivado desde el original (PDF) el 8 de julio de 2017 . Consultado el 8 de julio de 2017 .
- ^ Barrett, Paul (1987). "Implementación del algoritmo de cifrado de clave pública Rivest Shamir y Adleman en un procesador de señal digital estándar" . Actas sobre avances en criptología --- CRYPTO '86 . Londres, Reino Unido: Springer-Verlag. págs. 311–323. ISBN 0-387-18047-8.
- ^ Granlund, Torbjörn; Montgomery, Peter L. (junio de 1994). "División por números enteros invariantes mediante multiplicación" (PDF) . Avisos SIGPLAN . 29 (6): 61–72. CiteSeerX 10.1.1.1.2556 . doi : 10.1145 / 773473.178249 .
- ^ Möller, Niels; Granlund, Torbjörn (febrero de 2011). "División mejorada por enteros invariantes" (PDF) . Transacciones IEEE en computadoras . 60 (2): 165-175. doi : 10.1109 / TC.2010.143 . S2CID 13347152 .
- ^ ridiculous_fish. "Trabajo de división (episodio III): división sin firmar más rápida por constantes" . 2011.
- ^ LaBudde, Robert A .; Golovchenko, Nikolai; Newton, James; y Parker, David; Massmind: "División binaria por una constante"
- ^ Vocales, RA (1992). "División por 10". Revista informática australiana . 24 (3): 81–85.
Otras lecturas
- Warren Jr., Henry S. (2013). Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.
- Savard, John JG (2018) [2006]. "Técnicas aritméticas avanzadas" . quadibloc . Archivado desde el original el 3 de julio de 2018 . Consultado el 16 de julio de 2018 .