Algoritmo de división

Método de 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 , 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. Ejemplos de división lenta incluyen restauración, restauración no realizada, 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. ^[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á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 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 finalizar regresar  ( Q , R )

La prueba de que el cociente y el resto existen y son únicos (descrita en División euclidiana ) da lugar a un algoritmo de división completo, aplicable tanto a números negativos como positivos, mediante sumas, restas y comparaciones:

función  dividir ( N ​​,  D )  si  D  =  0  entonces  error ( DivisionByZero )  terminar  si  D  <  0  entonces  ( Q ,  R )  : =  dividir ( N ​​,  − D );  devolver  ( − Q ,  R )  terminar  si  N  <  0  entonces  ( Q , R )  : =  dividir ( − N ,  D )  si  R  =  0  entonces  devolver  ( − Q ,  0 )  en caso contrario  devolver  ( − Q  −  1 ,  D  −  R )  end  end  - En este punto, N ≥ 0 y D > 0  devuelve  divide_unsigned ( N ,  D ) end  function  divide_unsigned ( N ,  D )  Q  : =  0 ;  R  : =  N  mientras  R  ≥  D  hacer  Q  : =  Q  +  1  R  : =  R  −  D  fin  regresar  ( 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 los algoritmos de división lenta como la división larga. Es útil si se sabe que Q es pequeño (al ser un algoritmo sensible a la salida ) y puede servir como especificación ejecutable.

División larga

La división larga es el algoritmo estándar utilizado 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 luego se convierten en los dígitos del cociente, y la diferencia final es el resto.

Cuando se utiliza con una base binaria, este método forma la base para la división de enteros (sin signo) con el algoritmo de resto que se muestra a continuación. La división corta es una forma abreviada de división larga adecuada para divisores de un dígito. La fragmentación  , también conocida como método de los 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 restar más múltiplos de los que se tienen actualmente en cada etapa, también se puede desarrollar una variante más libre de división larga.

División entera (sin signo) con resto

El siguiente algoritmo, la versión binaria de la famosa división larga , dividirá N entre D , colocando el cociente en Q y el resto en R. En el siguiente pseudocó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 en cero R  : =  0  para  i  : =  n  −  1  ..  0  do  - Donde n es el número de bits en N  R  : =  R  <<  1  - Desplazamiento hacia la izquierda R 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  extremo extremo

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 (configurando R (0) a N(i))
Paso 5 : R < D, así que omita la declaración

Paso 2 : Establecer i=2
Paso 3 : R=010
Paso 4 : R=011
Paso 5 : R < D, declaración omitida

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 (estableciendo Q( i) a 1)

final
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 la base (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 0 menos significativo hasta el n −1 más significativo.
• n es el número de dígitos del cociente
• D es el divisor

Restaurando la división

La restauración de la división opera en números fraccionarios de punto fijo y depende del supuesto 0 < D < N . ^{[ cita necesaria ]}

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 desplazado (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  -- Bit de resultado 0  R :  = R  +  D  --  El nuevo resto parcial es (restablecido) valor desplazado  final-- Donde: N = numerador, D = denominador, n = #bits, R = resto parcial, q(i) = bit #i del cociente

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

División sin restauración

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 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 ningún paso de restauración después de la resta, ^[3] lo que potencialmente reduce el número de operaciones hasta a la mitad y permite que se ejecute más rápido. ^[4] 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  --  por ejemplo 31..0 para 32 bits si R >= 0 entonces q ( i ) : = + 1 R : = 2 * R − D else 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 está en una forma no estándar que consta de dígitos −1 y +1. Esta forma debe convertirse a binaria para formar el cociente final. Ejemplo:

Si los dígitos −1 de se almacenan como ceros (0) como es común, entonces la computación es trivial: realice un complemento a uno (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 siempre son 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 único paso de restauración después de que Q se convierta de una forma no estándar a una forma estándar:

si  R  <  0  entonces  Q  : =  Q  −  1  R  : =  R  +  D  -- Necesario sólo si el resto es de interés. terminara  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 consumen al mismo ritmo que se producen los bits del cociente Q, y es común utilizar un único registro de desplazamiento para ambos).

división SRT

La división SRT es un método popular de 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 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 radix-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 cociente no tiene por qué ser perfecta; Los dígitos del cociente posteriores pueden corregir errores leves. (Por ejemplo, los pares de dígitos cocientes (0, +2) y (1, −2) son equivalentes, ya que 0×4+2 = 1×4−2.) Esta tolerancia permite seleccionar los dígitos cocientes utilizando sólo 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 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 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 1.066 entradas se habían omitido por error. ^{[10] [11]}

Métodos de división rápida

División Newton-Raphson

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

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

1. Calcula una estimación del recíproco del divisor . ${\displaystyle X_{0}}$ ${\displaystyle 1/D}$ ${\displaystyle D}$
2. Calcule estimaciones sucesivamente 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 encontrar el recíproco de , es necesario encontrar 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 solo 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 multiplicaciones y sumas fusionadas . ${\displaystyle X_{i}}$

Desde el punto de vista computacional, 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 necesaria ]} 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 elevación al cuadrado 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 tener 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 se elige mal. ${\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; aplicando el mismo desplazamiento de bits al numerador N , se garantiza que el cociente no cambie. Entonces 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 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 con 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 polinómico de grado mayor que 1, calculando los coeficientes mediante el algoritmo de Remez . La desventaja es que la suposició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 lugares binarios. Esto se evalúa como 3 para precisión simple IEEE y 4 para formatos de doble precisión y doble extensión . ${\displaystyle P\,}$

Pseudocódigo

A continuación se 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 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' // precalcular constantes con la misma precisión que D tiempos de repetición  ${\displaystyle \left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}$   // se puede precalcular en función de P fijo X := X + X × (1 - D' × X)final 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 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

${\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 hacer que el error sea igual a un polinomio de Chebyshev de tercer orden reescalado de primera especie. Los coeficientes deben calcularse previamente y codificarse.

Luego, en el bucle, utilice una iteración que cubra 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 ciclo se realiza hasta que X concuerde con 1/ D en sus P bits 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 mayor grado, 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 gastarí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 Fi , elegido de manera que el divisor converja a 1. Esto hace que el dividendo converja a 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 Goldschmidt son:

1. Genere 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á lo suficientemente cerca de 1, devuelve el dividendo; de lo contrario, pasa al 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 se obtiene:

${\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 de IBM. ^{[16] [17]} Aunque converge al mismo ritmo que una implementación de Newton-Raphson, una ventaja del método Goldschmidt es que las multiplicaciones en el numerador y el denominador se pueden realizar en paralelo. ^[17]

Teorema del binomio

El método de Goldschmidt se puede utilizar con factores que permitan simplificaciones mediante el teorema del binomio . Supongamos que ha sido escalado por una potencia de dos tal que . Nosotros elegimos y . Esto produce ${\displaystyle N/D}$ ${\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 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; Esto ocurre frecuentemente, 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 la multiplicación por el método de Newton como se describe anteriormente, ^[18] así como la división ligeramente más rápida de Burnikel-Ziegler, ^[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 equivale 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 coma flotante el uso de (1/ D ) presenta pocos problemas, ^[a] pero en aritmética de enteros el recíproco siempre se evaluará como 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 dividir 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 enteros incluso cuando ( X / Y ) no es exactamente igual a 1/ D , pero está "lo suficientemente cerca" como para que el error introducido por la aproximación sea en los bits que son descartados por la operación de cambio. ^{[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 enteros sin signo de 32 bits, la división por 3 se puede reemplazar con una multiplicación por2863311531/2 ³³, una multiplicación por 2863311531 ( hexadecimal 0xAAAAAAAB) seguida de un desplazamiento de 33 bits a la derecha. El valor de 2863311531 se calcula como2 ³³/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 ³⁵ (o desplazamiento de 35 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 una 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/restas de x bits, una multiplicación de x bits por x bits (donde solo la mitad superior de se utiliza el resultado) y varios turnos, 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 lograr 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, de la que se obtiene el cociente exacto, con resto si es necesario. ^[27]

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 del Pentium FDIV

Notas

1. A pesar del "pequeño" problema que causa la optimización, esta optimización recíproca todavía suele estar oculta detrás de un indicador de "matemáticas rápidas" en los compiladores modernos , ya que es inexacta.
2. Los compiladores modernos suelen realizar 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). División entera de software (PDF) (Informe técnico). Investigación de Microsoft, Silicon Valley.
2. 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.
3. Shaw, Robert F. (1950). "Operaciones aritméticas en una computadora binaria". Revisión de Instrumentos Científicos . 21 (8): 690. Código bibliográfico : 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 de aritmética informática avanzada) - Folleto del capítulo 5 (División)" (PDF) . Universidad Stanford . Archivado (PDF) desde el original el 18 de abril de 2022 . Consultado el 24 de junio de 2019 .
5. Harris, David L.; Oberman, Stuart F.; Horowitz, Mark A. (9 de septiembre de 1998). División SRT: Arquitecturas, Modelos e Implementaciones (PDF) (Reporte técnico). Universidad Stanford. Archivado (PDF) desde el original el 24 de diciembre de 2016 . Consultado el 23 de diciembre de 2016 .
6. McCann, marca; Pippenger, Nicolás (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. Archivado desde el original el 24 de agosto de 2022 . Consultado el 24 de agosto de 2022 . 
7. Cocke, Juan; Sweeney, DW (11 de febrero de 1957), Aritmética de alta velocidad en un dispositivo paralelo (Company Memo), IBM, p. 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 (1 de septiembre de 1958). "Una nueva clase de métodos de división digital". Transacciones IRE en Computadoras Electrónicas . IEEE. CE-7 (3): 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". La Revista Trimestral de Mecánica y Matemática Aplicada . 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 fallas de coma flotante". Corporación Intel. 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 implementaciones y algoritmos de división (PDF) (Reporte técnico). Universidad 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 división por convergencia (PDF) (Tesis). Maestría en Ciencias disertación. MIT OCLC  34136725. Archivado (PDF) desde el original el 10 de diciembre de 2015 . Consultado el 15 de septiembre de 2015 .
13. "Autores". Revista IBM de investigación y desarrollo . 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 e implementación de división en coma flotante y raíz cuadrada en el Microprocesador AMD-K7TM" (PDF) . Actas del 14º Simposio IEEE sobre aritmética informática (n.º de catálogo 99CB36336) . págs. 106-115. doi :10.1109/ARITH.1999.762835. ISBN 0-7695-0116-8. S2CID  12793819. Archivado (PDF) desde el 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: elegir la implementación adecuada". Micro IEEE . 17 (4): 56–66. doi : 10.1109/40.612224.
16. 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
17. Guy, incluso; Pedro, 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 enteros grandes: una comparación de algoritmos (PDF) (tesis de maestría en informática). Real Instituto de Tecnología. 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 de 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 6 de junio de 2019 . Consultado el 8 de diciembre de 2015 . 
22. 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. Archivado (PDF) desde el original el 22 de diciembre de 2015 . Consultado el 8 de diciembre de 2015 .
23. pez_ridículo. "Trabajo de división (Episodio III): División sin firmar más rápida mediante constantes" Archivado el 8 de enero de 2022 en Wayback Machine . 2011.
24. pez_ridículo. "libdivide, división entera optimizada". Archivado desde el original el 23 de noviembre de 2021 . Consultado el 6 de julio de 2021 .
25. Warren Jr., Henry S. (2013). El placer del hacker (2 ed.). 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 australiana de informática . 24 (3): 81–85.

Otras lecturas

• Savard, John JG (2018) [2006]. "Técnicas Aritméticas Avanzadas". cuadribloc . Archivado desde el original el 3 de julio de 2018 . Consultado el 16 de julio de 2018 .