Algoritmo de división

Método para la división con resto

Un algoritmo de división es un algoritmo que, dados dos números enteros N y D (respectivamente el numerador y el denominador), calcula su cociente y/o resto , el resultado de la división euclidiana . Algunos se aplican a mano, mientras que otros se emplean en diseños de circuitos digitales y software.

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. Algunos ejemplos de división lenta son la división restauradora, la división restauradora sin rendimiento, la división sin restauración y la 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. ^[1] Los algoritmos de Newton-Raphson y Goldschmidt entran en esta categoría.

Las variantes de estos algoritmos permiten utilizar algoritmos de multiplicación rápidos . El resultado es que, para números enteros grandes, el tiempo de computación 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 utilizado.

La discusión se referirá al formulario , donde ${\displaystyle N/D=(Q,R)}$

• 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 los Elementos de Euclides , Libro VII, Proposición 1, encuentra el resto dados dos números enteros positivos usando solo restas y comparaciones:

R  : =  N Q  : =  0 mientras  R  ≥  D  hacer  R  : =  R  −  D  Q  : =  Q  +  1 fin devolver  ( Q , 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, aplicable tanto a números negativos como positivos, utilizando sumas, restas y comparaciones:

función  dividir ( N ​​,  D )  si  D  =  0  entonces  error ( DivisionByZero )  fin  si  D  <  0  entonces  ( Q ,  R )  : =  dividir ( N ​​,  − D );  devolver  ( − Q ,  R )  fin  si  N  <  0  entonces  ( Q , R )  : =  dividir ( − N ,  D )  si  R  =  0  entonces  devolver  ( − Q ,  0 )  de lo contrario  devolver  ( − Q  −  1 ,  D  −  R )  fin  fin  -- En este punto, N ≥ 0 y D > 0  devolver  dividir_sin signo ( N ,  D ) fin  función  dividir_sin signo ( N ,  D )  Q  : =  0 ;  R  : =  N  mientras  R  ≥  D  hacer  Q  : =  Q  +  1  R  : =  R  −  D  fin  devolver  ( Q ,  R ) fin

Este procedimiento siempre produce R ≥ 0. Aunque es muy simple, requiere Ω(Q) pasos y, por lo tanto, es exponencialmente más lento que incluso algoritmos de división lentos como la división larga. Es útil si se sabe que Q es pequeño (al tratarse de 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 dividir números de varios dígitos expresados ​​en notación decimal con lápiz y papel. Se desplaza gradualmente desde el extremo izquierdo al derecho del dividendo, restando el mayor múltiplo posible del divisor (a nivel de dígito) en cada etapa; los múltiplos se convierten entonces en los dígitos del cociente y la diferencia final es el resto.

Cuando se utiliza con un radio binario, este método forma la base para el algoritmo de división de enteros (sin signo) con resto que se muestra a continuación. La división corta es una forma abreviada de la división larga adecuada para divisores de un dígito. La división por partes  , también conocida 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 la división larga.

División de enteros (sin signo) con resto

El siguiente algoritmo, la versión binaria de la famosa división larga , dividirá N por D , colocando el cociente en Q y el resto en R. En el siguiente pseudocódigo, todos los valores se tratan como números enteros sin signo.

si  D  =  0  entonces  error ( DivisionByZeroException )  fin Q  : =  0  -- Inicializa el cociente y el resto a cero R  : =  0  para  i  : =  n  −  1  ..  0  hacer  -- Donde n es el número de bits en N  R  : =  R  <<  1  -- Desplaza R a la izquierda en 1 bit  R ( 0 )  : =  N ( i )  -- Establece el bit menos significativo de R igual al bit i del numerador  si  R  ≥  D  entonces  R  : =  R  −  D  Q ( i )  : =  1  fin fin

Ejemplo

Si tomamos N=1100 ₂ (12 ₁₀ ) y D=100 ₂ (4 ₁₀ )

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 (establezca R(0) en N(i))
Paso 5 : R < D, por lo que omita la declaración

Paso 2 : Establezca i=2
Paso 3 : R=010
Paso 4 : R=011
Paso 5 : R < D, se omite la instrucción

Paso 2 : Establezca i=1
Paso 3 : R=0110
Paso 4 : R=0110
Paso 5 : R>=D, instrucción ingresada
Paso 5b : R=10 (R−D)
Paso 5c : Q=10 (establezca Q(i) en 1)

Paso 2 : Establezca i=0
Paso 3 : R=100
Paso 4 : R=100
Paso 5 : R>=D, instrucción ingresada
Paso 5b : R=0 (R−D)
Paso 5c : Q=11 (establezca Q(i) en 1)

fin
Q=11 ₂ (3 ₁₀ ) 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]

${\displaystyle R_{j+1}=B\times R_{j}-q_{n-(j+1)}\times D,}$

dónde:

• R _j es el j -ésimo resto parcial de la división
• B es el radix (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 están numeradas desde el menos significativo 0 hasta el más significativo n −1
• n es el número de dígitos del cociente
• D es el divisor

Restaurando la división

La división restauradora opera sobre números fraccionarios de punto fijo 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 la división restauradora 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  -- Prueba de resta del valor desplazado (la multiplicación por 2 es un desplazamiento en la representación binaria)  si  R  >=  0  entonces  q ( i )  : =  1  -- Bit de resultado 1  de lo contrario  q ( i )  : =  0  -- Bit de resultado 0  R  : =  R  +  D  -- El nuevo resto parcial es (se restaura) el valor desplazado  fin fin-- Donde: N = numerador, D = denominador, n = #bits, R = resto parcial, q(i) = bit #i del cociente

La división restauradora sin ejecución es similar a la división restauradora excepto que se guarda el valor de 2R, por lo que no es necesario volver a agregar D en el caso de que R < 0.

División no restaurativa

La división sin recuperació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 tiene la ventaja cuando se implementa en hardware de que solo hay una decisión y una suma/resta por bit de cociente; no hay un paso de recuperación después de la resta, ^[3] lo que potencialmente reduce la cantidad de operaciones hasta la mitad y permite que se ejecute más rápido. ^[4] El algoritmo básico para la división binaria (raíz 2) sin recuperació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  hacer  -- por ejemplo 31..0 para 32 bits  si  R  >=  0  entonces  q ( i )  : =  + 1  R  : =  2  *  R  −  D  de lo contrario  q ( i )  : =  − 1  R  : =  2  *  R  +  D  fin  si fin -- Nota: N=numerador, D=denominador, n=#bits, R=resto parcial, q(i)=bit #i del cociente.

Siguiendo este algoritmo, el cociente tiene una forma no estándar que consta de los dígitos −1 y +1. Esta forma debe convertirse a binario para formar el cociente final. Ejemplo:

Si los dígitos −1 de se almacenan como ceros (0) como es común, entonces es y el cálculo es trivial: realice un complemento de unos (complemento bit a bit) en el original . ${\displaystyle Q}$ ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle M}$ ${\displaystyle Q}$

Q  : =  Q  −  bit . bnot ( Q )  – Apropiado si −1 dígitos en Q se representan 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 < D. Por ejemplo, 5 / 2 = 3 R −1. Para convertir a un resto positivo, realice un solo paso de restauración después de convertir Q de la forma no estándar a la forma estándar:

si  R  <  0  entonces  Q  : =  Q  −  1  R  : =  R  +  D  -- Necesario sólo si el resto es de interés. fin  si

El resto real es R >> n. (Al igual que con la división restauradora, 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

La división SRT es un método popular para la división en muchas implementaciones de microprocesadores . ^{[5] [6]} El algoritmo lleva el nombre de DW Sweeney de IBM , James E. Robertson de la Universidad de Illinois y KD Tocher del Imperial College de Londres . Todos ellos desarrollaron el algoritmo de forma independiente aproximadamente al mismo tiempo (publicado en febrero de 1957, septiembre de 1958 y enero de 1958 respectivamente). ^{[7] [8] [9]}

La división SRT es similar a la división sin restauración, pero utiliza 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 SRT de base 4, 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 del cociente no necesita ser perfecta; los dígitos del cociente posteriores 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 dígitos del cociente utilizando solo algunos bits más significativos del dividendo y divisor, en lugar de requerir una resta de ancho completo. Esta simplificación, a su vez, permite utilizar un radio mayor que 2.

Al igual que en la división sin restauración, los pasos finales son una resta final de ancho completo para resolver el último bit del cociente y la conversión del cociente a forma binaria estándar.

El infame error de división en coma flotante del procesador Intel Pentium fue causado por una tabla de búsqueda mal codificada. Se habían omitido por error cinco de las 1066 entradas. ^{[10] [11]}

Métodos de división rápida

División Newton-Raphson

Newton-Raphson utiliza el método de Newton para encontrar el recíproco de y multiplicar ese recíproco por para encontrar el cociente final . ${\displaystyle D}$ ${\displaystyle N}$ ${\displaystyle Q}$

Los pasos de la división de Newton-Raphson son:

1. Calcular una estimación para el recíproco del divisor . ${\displaystyle X_{0}}$ ${\displaystyle 1/D}$ ${\displaystyle D}$
2. Calcular estimaciones cada vez más precisas del recíproco. Aquí es donde se emplea el método de Newton-Raphson como tal. ${\displaystyle X_{1},X_{2},\ldots ,X_{S}}$
3. Calcula el cociente multiplicando el dividendo por el recíproco del divisor: . ${\displaystyle Q=NX_{S}}$

Para aplicar el método de Newton para hallar el recíproco de , es necesario hallar una función que tenga un cero en . La función obvia es , pero la iteración de Newton-Raphson para esto no es útil, ya que no se puede calcular sin conocer ya 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 sí funciona es , para la cual la iteración de Newton-Raphson da ${\displaystyle D}$ ${\displaystyle f(X)}$ ${\displaystyle X=1/D}$ ${\displaystyle f(X)=DX-1}$ ${\displaystyle D}$ ${\displaystyle f(X)=(1/X)-D}$

$${\displaystyle X_{i+1}=X_{i}-{f(X_{i}) \over f'(X_{i})}=X_{i}-{1/X_{i}-D \over -1/X_{i}^{2}}=X_{i}+X_{i}(1-DX_{i})=X_{i}(2-DX_{i}),}$$

que se puede calcular usando solo multiplicación y resta, o usando dos operaciones de multiplicación-suma fusionadas . ${\displaystyle X_{i}}$

Desde un punto de vista computacional, las expresiones y no son equivalentes. Para obtener un resultado con una precisión de 2 n bits al hacer uso de 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 solo necesita calcularse con una precisión de n bits, porque los n bits iniciales (después del punto binario) de son ceros. ${\displaystyle X_{i+1}=X_{i}+X_{i}(1-DX_{i})}$ ${\displaystyle X_{i+1}=X_{i}(2-DX_{i})}$ ${\displaystyle X_{i}}$ ${\displaystyle (2-DX_{i})}$ ${\displaystyle X_{i}}$ ${\displaystyle X_{i}}$ ${\displaystyle (1-DX_{i})}$ ${\displaystyle (1-DX_{i})}$

Si el error se define como , entonces: ${\displaystyle \varepsilon _{i}=1-DX_{i}}$

${\displaystyle {\begin{aligned}\varepsilon _{i+1}&=1-DX_{i+1}\\&=1-D(X_{i}(2-DX_{i}))\\&=1-2DX_{i}+D^{2}X_{i}^{2}\\&=(1-DX_{i})^{2}\\&={\varepsilon _{i}}^{2}.\\\end{aligned}}}$

Esta cuadratura del error en cada paso de 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 en 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 los 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 elegida. ${\displaystyle X_{0}}$

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; al aplicar el mismo desplazamiento de bits al numerador N , se asegura que el cociente no cambie. Luego se podría utilizar una aproximación lineal en la forma ${\displaystyle X_{0}}$

${\displaystyle X_{0}=T_{1}+T_{2}D\approx {\frac {1}{D}}\,}$

para inicializar Newton–Raphson. Para minimizar el máximo del valor absoluto del error de esta aproximación en el intervalo , se debe utilizar ${\displaystyle [0.5,1]}$

${\displaystyle X_{0}={48 \over 17}-{32 \over 17}D.\,}$

Los coeficientes de la aproximación lineal se determinan de la siguiente manera. El valor absoluto del error es . El mínimo del valor absoluto máximo del error se determina mediante 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 ${\displaystyle |\varepsilon _{0}|=|1-D(T_{1}+T_{2}D)|}$ ${\displaystyle F(D)=1-D(T_{1}+T_{2}D)}$ ${\displaystyle F(D)}$ ${\displaystyle F'(D)=0}$ ${\displaystyle D=-T_{1}/(2T_{2})}$ ${\displaystyle F(1/2)=F(1)=-F(-T_{1}/(2T_{2}))}$ ${\displaystyle T_{1}=48/17}$ ${\displaystyle T_{2}=-32/17}$ ${\displaystyle F(1)=1/17}$

${\displaystyle \vert \varepsilon _{0}\vert \leq {1 \over 17}\approx 0.059.\,}$

Es posible generar un ajuste polinomial de grado mayor que 1, calculando los coeficientes utilizando el algoritmo Remez . La desventaja es que la estimación 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

${\displaystyle S=\left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}$

Los pasos son suficientes para calcular el valor hasta los dígitos binarios. Esto se evalúa como 3 para la precisión simple IEEE y 4 para los formatos de precisión doble y doble extendido . ${\displaystyle P\,}$

Pseudocódigo

A continuación se calcula el cociente de N y D con una precisión de P lugares binarios:

Expresar D como M × 2 e donde 1 ≤ M < 2 (representación de punto 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' // precalcula constantes con la misma precisión que los tiempos de repetición  ${\displaystyle \left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}$   D // se pueden precalcular en función de P fijo X := X + X × (1 - D' × X)fin retorno N' × X

Por ejemplo, para una división de punto flotante de doble precisión, este método utiliza 10 multiplicaciones, 9 sumas 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 desplazar N y D de modo que D esté en [0,5, 1,0], inicialice con

${\displaystyle X:={\frac {140}{33}}+D\cdot \left({\frac {-64}{11}}+D\cdot {\frac {256}{99}}\right).}$

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 que el error sea igual a un polinomio de Chebyshev de tercer orden reescalado de primera clase. Los coeficientes deben calcularse previamente y codificarse de forma fija.

Luego, en el bucle, utilice una iteración que eleve al cubo el error.

${\displaystyle E:=1-D\cdot X}$

${\displaystyle Y:=X\cdot E}$

${\displaystyle X:=X+Y+Y\cdot E.}$

El término Y ⋅ E es nuevo.

Si el bucle se ejecuta hasta que X concuerde con 1/ D en sus bits P iniciales , entonces el número de iteraciones no será mayor que

${\displaystyle \left\lceil \log _{3}\left({\frac {P+1}{\log _{2}99}}\right)\right\rceil }$

que es el número de veces que se debe elevar al cubo 99 para llegar a 2 ^{P +1} . Entonces

${\displaystyle Q:=N\cdot X}$

es el cociente de P bits.

El uso de polinomios de grado superior, ya sea en la inicialización o en la iteración, da como resultado una degradación del rendimiento porque las multiplicaciones adicionales requeridas se emplearían mejor en realizar más iteraciones.

División Goldschmidt

La división de Goldschmidt ^[12] (según Robert Elliott Goldschmidt) ^[13] utiliza un proceso iterativo de multiplicar repetidamente tanto el dividendo como el divisor por un factor común F _i , elegido de manera que el divisor converja a 1. Esto hace que el dividendo converja al cociente buscado Q :

${\displaystyle Q={\frac {N}{D}}{\frac {F_{1}}{F_{1}}}{\frac {F_{2}}{F_{2}}}{\frac {F_{\ldots }}{F_{\ldots }}}.}$

Los pasos para la división de Goldschmidt son:

1. Generar una estimación para el factor de multiplicación F _i .
2. Multiplica el dividendo y el divisor por F _i .
3. Si el divisor está suficientemente cerca de 1, devuelve el dividendo; de lo contrario, repite el bucle hasta el paso 1.

Suponiendo que N / D se ha escalado de modo que 0 <  D  < 1, cada F _i se basa en D :

${\displaystyle F_{i+1}=2-D_{i}.}$

Multiplicando el dividendo y el divisor por el factor obtenemos:

${\displaystyle {\frac {N_{i+1}}{D_{i+1}}}={\frac {N_{i}}{D_{i}}}{\frac {F_{i+1}}{F_{i+1}}}.}$

Después de un número suficiente k de iteraciones . ${\displaystyle Q=N_{k}}$

El método Goldschmidt se utiliza en las CPU AMD Athlon y modelos posteriores. ^{[14] [15]} También se conoce como algoritmo Anderson Earle Goldschmidt Powers (AEGP) y se implementa en varios procesadores IBM. ^{[16] [17]} Aunque converge a la misma velocidad que una implementación de Newton-Raphson, una ventaja del método Goldschmidt es que las multiplicaciones en el numerador y en el denominador se pueden realizar en paralelo. ^[17]

Teorema del binomio

El método de Goldschmidt se puede utilizar con factores que permiten simplificaciones mediante el teorema binomial . Supongamos que ⁠ ⁠ ${\displaystyle N/D}$ ha sido escalado por una potencia de dos tal que . Elegimos y . Esto da como resultado ${\displaystyle D\in \left({\tfrac {1}{2}},1\right]}$ ${\displaystyle D=1-x}$ ${\displaystyle F_{i}=1+x^{2^{i}}}$

$${\displaystyle {\frac {N}{1-x}}={\frac {N\cdot (1+x)}{1-x^{2}}}={\frac {N\cdot (1+x)\cdot (1+x^{2})}{1-x^{4}}}=\cdots =Q'={\frac {N'=N\cdot (1+x)\cdot (1+x^{2})\cdot \cdot \cdot (1+x^{2^{(n-1)}})}{D'=1-x^{2^{n}}\approx 1}}}$$.

Después de n pasos , el denominador se puede redondear a ${\displaystyle \left(x\in \left[0,{\tfrac {1}{2}}\right)\right)}$ ${\displaystyle 1-x^{2^{n}}}$1 con un error relativo

${\displaystyle \varepsilon _{n}={\frac {Q'-N'}{Q'}}=x^{2^{n}}}$

que es máximo en cuando , proporcionando así una precisión mínima de dígitos binarios. ${\displaystyle 2^{-2^{n}}}$ ${\displaystyle x={\tfrac {1}{2}}}$ ${\displaystyle 2^{n}}$

Métodos de números enteros grandes

Los métodos diseñados para la implementación de hardware generalmente no escalan a números enteros con miles o millones de dígitos decimales; esto ocurre 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 un pequeño número de multiplicaciones, que luego se pueden realizar utilizando 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 la multiplicación por el método de Newton como se describió anteriormente, ^[18] así como la división de Burnikel-Ziegler ligeramente más rápida, ^[19] la reducción de Barrett y los algoritmos de reducción de Montgomery . ^{[20] [ 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 solo 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 . Como el denominador es constante, también lo es su recíproco (1/ D ). Por lo tanto, 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 N/D . En aritmética de punto flotante , el uso de (1/ D ) presenta pocos problemas, ^[a] pero en aritmética de números enteros el recíproco siempre se evaluará como cero (suponiendo que | 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 utilizar 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 bit 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 ) se evaluará como cero.

Sin embargo, a menos que D sea una potencia de dos, no hay X ni Y que satisfagan las condiciones anteriores. Afortunadamente, ( N · X )/ Y da exactamente el mismo resultado que N / D en aritmética de números enteros incluso cuando ( X / Y ) no es exactamente igual a 1/ D , pero "lo suficientemente cerca" como para que el error introducido por la aproximación esté en los bits que se descartan por la operación de desplazamiento. ^{[21] [22] [23]} La reducción de Barrett utiliza potencias de 2 para el valor de Y para hacer que la división por Y sea un simple desplazamiento a la derecha. ^[b]

Como ejemplo concreto de aritmética de punto fijo , para números enteros sin signo de 32 bits, la división por 3 se puede reemplazar por una multiplicación por ⁠2863311531/2 ³³⁠ , 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 ³³/3⁠ , luego se redondea hacia arriba. Del mismo modo, la división por 10 se puede expresar como una multiplicación por 3435973837 (0xCCFVCD) seguida de una división por 2 ³⁵ (o 35 desplazamiento de bits a la derecha). ^{[25] : p230-234} OEIS proporciona secuencias de las constantes para la multiplicación como A346495 y para el desplazamiento a la derecha como A346496.

Para la división general de enteros sin signo de x bits donde el divisor D no es una potencia de 2, la siguiente identidad convierte la división en dos sumas/resta de x bits, una multiplicación de x bit por x bit (donde solo se utiliza la mitad superior del resultado) y varios desplazamientos, después de precalcular y : ${\displaystyle k=x+\lceil \log _{2}{D}\rceil }$ ${\displaystyle a=\left\lceil {\frac {2^{k}}{D}}\right\rceil -2^{x}}$

${\displaystyle \left\lfloor {\frac {N}{D}}\right\rfloor =\left\lfloor {\frac {\left\lfloor {\frac {N-b}{2}}\right\rfloor +b}{2^{k-x-1}}}\right\rfloor {\text{ where }}b=\left\lfloor {\frac {Na}{2^{x}}}\right\rfloor }$

En algunos casos, la división por una constante se puede realizar en incluso menos tiempo convirtiendo la "multiplicación por una constante" en una serie de desplazamientos y sumas o restas . ^[26] De particular interés es la división por 10, para la cual se obtiene el cociente exacto, con resto si es necesario. ^[27]

Error de redondeo

Cuando se realiza una operación de división, el cociente y el resto exactos se aproximan para ajustarse a los límites de precisión de la computadora. El algoritmo de división establece: ${\displaystyle q}$ ${\displaystyle r}$

${\displaystyle [a=bq+r]}$

dónde . ${\displaystyle 0\leq r<|b|}$

En aritmética de punto flotante , el cociente se representa como y el resto como , lo que introduce errores de redondeo y : ${\displaystyle q}$ ${\displaystyle {\tilde {q}}}$ ${\displaystyle r}$ ${\displaystyle {\tilde {r}}}$ ${\displaystyle \epsilon _{q}}$ ${\displaystyle \epsilon _{q}}$ ${\displaystyle \epsilon _{r}}$

${\displaystyle [{\tilde {q}}=q+\epsilon _{q}][{\tilde {r}}=r+\epsilon _{r}]}$

Este redondeo provoca un pequeño error, que puede propagarse y acumularse a través de cálculos posteriores. Estos errores son particularmente pronunciados en procesos iterativos y cuando se restan valores casi iguales, lo que se conoce como pérdida de significancia . Para mitigar estos errores, se emplean técnicas como el uso de dígitos de guarda o aritmética de mayor precisión. ^{[28] [29]}

Véase también

• División de galeras
• Algoritmo de multiplicación
• Error FDIV en Pentium

Notas

1. A pesar de lo "pequeño" que es el problema que causa la optimización, esta optimización recíproca todavía suele estar oculta detrás de un indicador de "matemática rápida" en los compiladores modernos , ya que es inexacta.
2. Los compiladores modernos comúnmente realizan esta optimización de multiplicación y desplazamiento de números enteros; sin embargo, para una constante que sólo se conoce en tiempo de ejecución, el programa debe implementar la optimización por sí mismo. ^[24]

Referencias

1. Rodeheffer, Thomas L. (26 de agosto de 2008). Software Integer Division (PDF) (informe técnico). Microsoft Research, Silicon Valley.
2. Morris, James E.; Iniewski, Krzysztof (22 de noviembre de 2017). Manual de aplicaciones de dispositivos nanoelectrónicos. CRC Press. ISBN 978-1-351-83197-0.
3. Shaw, Robert F. (1950). "Operaciones aritméticas en una computadora binaria". Review of Scientific Instruments . 21 (8): 690. Bibcode :1950RScI...21..687S. doi :10.1063/1.1745692. ISSN  0034-6748. Archivado desde el original el 28 de febrero de 2022 . Consultado el 28 de febrero de 2022 .
4. Flynn. «Stanford EE486 (División aritmética informática avanzada) – Capítulo 5 Folleto (División)» (PDF) . Universidad de Stanford . Archivado (PDF) desde el original el 2022-04-18 . Consultado el 2019-06-24 .
5. 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 de Stanford. Archivado (PDF) del original el 24 de diciembre de 2016. Consultado el 23 de diciembre de 2016 .
6. McCann, Mark; Pippenger, Nicholas (2005). "Algoritmos de división SRT como sistemas dinámicos". Revista SIAM de informática . 34 (6): 1279–1301. CiteSeerX 10.1.1.72.6993 . doi :10.1137/S009753970444106X. hdl :2429/12179. Archivado desde el original el 24 de agosto de 2022 . Consultado el 24 de agosto de 2022 . 
7. Cocke, John; Sweeney, DW (11 de febrero de 1957), Aritmética de alta velocidad en un dispositivo paralelo (Memorando de la empresa), IBM, pág. 20, archivado desde el original el 24 de agosto de 2022 , consultado el 24 de agosto de 2022{{citation}}: CS1 maint: location missing publisher (link)
8. Robertson, James (1958-09-01). "Una nueva clase de métodos de división digital". IRE Transactions on Electronic Computers . EC-7 (3). IEEE: 218–222. doi :10.1109/TEC.1958.5222579. hdl : 2027/uiuo.ark:/13960/t0gt7529c . Archivado desde el original el 24 de agosto de 2022 . Consultado el 24 de agosto de 2022 .
9. Tocher, KD (1 de enero de 1958). «Técnicas de multiplicación y división para computadoras binarias automáticas». The Quarterly Journal of Mechanics and Applied Mathematics . 11 (3): 364–384. doi :10.1093/qjmam/11.3.364. Archivado desde el original el 24 de agosto de 2022 . Consultado el 24 de agosto de 2022 .
10. "Análisis estadístico de la falla de punto flotante". Intel Corporation. 1994. Archivado desde el original el 23 de octubre de 2013. Consultado el 22 de octubre de 2013 .
11. Oberman, Stuart F.; Flynn, Michael J. (julio de 1995). Un análisis de algoritmos e implementaciones de división (PDF) (informe técnico). Universidad de Stanford. CSL-TR-95-675. Archivado (PDF) desde el original el 17 de mayo de 2017. Consultado el 23 de diciembre de 2016 .
12. Goldschmidt, Robert E. (1964). Aplicaciones de la división por convergencia (PDF) (Tesis). Tesis de maestría. MIT OCLC  34136725. Archivado (PDF) desde el original el 2015-12-10 . Consultado el 2015-09-15 .
13. "Autores". IBM Journal of Research and Development . 11 : 125–127. 1967. doi :10.1147/rd.111.0125. Archivado desde el original el 18 de julio de 2018.
14. Oberman, Stuart F. (1999). "Algoritmos de división de punto flotante y raíz cuadrada e implementación en el microprocesador AMD-K7" (PDF) . Actas del 14.º Simposio IEEE sobre aritmética informática (Cat. N.º 99CB36336) . pp. 106–115. doi :10.1109/ARITH.1999.762835. ISBN . 0-7695-0116-8. S2CID  12793819. Archivado (PDF) del original el 29 de noviembre de 2015. Consultado el 15 de septiembre de 2015 .
15. Soderquist, Peter; Leeser, Miriam (julio-agosto de 1997). "División y raíz cuadrada: elección de la implementación correcta". IEEE Micro . 17 (4): 56–66. doi :10.1109/40.612224.
16. SF Anderson, JG Earle, RE Goldschmidt, DM Powers. El modelo 91 de IBM 360/370: unidad de ejecución de punto flotante , IBM Journal of Research and Development , enero de 1997
17. Guy, Even; Peter, Siedel; Ferguson, Warren (1 de febrero de 2005). "Un análisis de error paramétrico del algoritmo de división de Goldschmidt". Revista de Ciencias de la Computación y de Sistemas . 70 (1): 118–139. doi : 10.1016/j.jcss.2004.08.004 .
18. 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). Royal Institute of Technology. Archivado desde el original (PDF) el 8 de julio de 2017. Consultado el 8 de julio de 2017 .
19. Joachim Ziegler, Christoph Burnikel (1998), División recursiva rápida, Max-Planck-Institut für Informatik, archivado desde el original el 26 de abril de 2011 , consultado el 10 de septiembre de 2021{{citation}}: CS1 maint: location missing publisher (link)
20. 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.
21. Granlund, Torbjörn; Montgomery, Peter L. (junio de 1994). «División por enteros invariantes mediante multiplicación» (PDF) . Avisos SIGPLAN . 29 (6): 61–72. CiteSeerX 10.1.1.1.2556 . doi :10.1145/773473.178249. Archivado (PDF) desde el original el 2019-06-06 . Consultado el 2015-12-08 . 
22. Möller, Niels; Granlund, Torbjörn (febrero de 2011). "División mejorada por enteros invariantes" (PDF) . IEEE Transactions on Computers . 60 (2): 165–175. doi :10.1109/TC.2010.143. S2CID  13347152. Archivado (PDF) desde el original el 22 de diciembre de 2015 . Consultado el 8 de diciembre de 2015 .
23. ridículo_pez. "Trabajo de división (Episodio III): División más rápida sin signo por constantes" Archivado el 8 de enero de 2022 en Wayback Machine . 2011.
24. ridículo_pescado. «libdivide, división de enteros optimizada». Archivado desde el original el 23 de noviembre de 2021. Consultado el 6 de julio de 2021 .
25. Warren Jr., Henry S. (2013). Hacker's Delight (2.ª edición). Addison Wesley - Pearson Education, Inc. ISBN  978-0-321-84268-8.
26. LaBudde, Robert A.; Golovchenko, Nikolai; Newton, James; y Parker, David; Massmind: "División binaria por una constante" Archivado el 9 de enero de 2022 en Wayback Machine.
27. Vocales, RA (1992). "División por 10". Revista informática australiana . 24 (3): 81–85.
28. L. Popyack, Jeffrey (junio de 2000). "Error de redondeo". Universidad de Drexel .
29. "9. Números de máquina, error de redondeo y propagación de errores". College of Charleston . 8 de febrero de 2021.

Lectura adicional

• Savard, John JG (2018) [2006]. «Técnicas aritméticas avanzadas». quadibloc . Archivado desde el original el 2018-07-03 . Consultado el 2018-07-16 .