Algoritmo de división

A división algoritmo es un algoritmo que, dado 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 Euclideana. Algunos se aplican a mano, mientras que otros son empleados por los diseños de circuitos digitales y el software.

Los algoritmos de división entran 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 la restauración, la restauración no funcional, la no restauración y la división SRT. Los métodos de división rápido 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 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.

El debate se refiere al formulario ${\displaystyle N/D=(Q,R)}$, donde

• 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 enteros positivos usando solo restas y comparaciones:

R := NQ := 0mientras R ≥ D do R := R − D Q := Q + 1finalRegreso ()Q,R)

La prueba de que el cociente y el resto existen y son únicos (descrito en la división Euclidean) da lugar a un algoritmo de división completo, aplicable tanto a números negativos como positivos, utilizando adiciones, subtracciones y comparaciones:

función dividir()N, D) si D = 0 entonces error()DivisionByZero) final si D c) 0 entonces ()Q, R) := dividir()N, −D); Regreso ()−Q, R) final si N c) 0 entonces ()Q,R) := dividir()−N, D) si R = 0 entonces Regreso ()−Q, 0) más Regreso ()−Q − 1, D − R) final final -- En este punto, N ≥ 0 y D 0 Regreso divide_unsigned()N, D)final función divide_unsigned()N, D) Q := 0; R := N mientras R ≥ D do Q := Q + 1 R := R − D final Regreso ()Q, R)final

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 lentos 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 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 enteros sin signo.

si D = 0 entonces error()DivisionByZeroException) finalQ := 0 - Iniciar el cociente y permanecer en ceroR := 0 para i := n − 1 .. 0 do -- Donde n es número de bits en N R := R c) c) 1 - Izquierda R por 1 bit R()0) := N()i) -- Establecer el bit menos significativo de R igual al bit i del numerador si R ≥ D entonces R := R − D Q()i) := 1 finalfinal

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 1 a la izquierda)
Paso 4: R=01 (estableciendo R(0) en N(i))
Paso 5: R < D, así que omite 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 (estableciendo Q(i) en 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) 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

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

donde:

• R_j es j- el resto parcial de la división
• B es el radio (base, generalmente 2 internamente en computadoras y calculadoras)
• q _{n −j + 1)} es el dígito del cociente en posición n−j+1), donde las posiciones del dígito se numeran de menos significativo 0 a la más significativa n−1
• n es el número de dígitos en el cociente
• D es el divisor

Restauración de la división

La división de restauración funciona con números fraccionados de punto fijo y depende de la suposición 0 D c) N.

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 de restauración binaria (radix 2) es:

R := ND := D c) c) n -- R y D necesitan el doble de ancho de palabra de N y Qpara i := n − 1 .. 0 do -- Por ejemplo 31..0 para 32 bits R := 2 * R − D -- La resta de prueba del valor desplazado (multiplicación por 2 es un cambio en la representación binaria) si R >= 0 entonces q()i) := 1 - Resultado 1 más q()i) := 0 - Resultado 0 R := R + D -- Nuevo restante parcial es (restorsionado) el valor desplazado finalfinal-- Donde: N = numerador, D = denominador, n = #bits, R = restante parcial, q(i) = bit #i de 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, lo que potencialmente reduce el número de operaciones hasta a la mitad y permite que se ejecute más rápido. El algoritmo básico para la división binaria (base 2) sin restauración de números no negativos es:

R := ND := D c) c) n -- R y D necesitan el doble de ancho de palabra de N y Qpara i = n − 1 .. 0 do - por ejemplo 31..0 para 32 bits si R >= 0 entonces q()i) := +1 R := 2 * R − D más q()i) := −1 R := 2 * R + D final sifinal-- Note: N=numerator, D=denominator, n=#bits, R=partial remainder, q(i)=bit #i of quotient.

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:

Convertir el siguiente coeficiente en el conjunto de dígitos {0,1}:
Comienzo:	${\displaystyle Q=111{\bar {1}1{\bar {1}1{\bar}1{\bar {1}}$
1. Forma el término positivo:	${\displaystyle P=11101010\,}$
2. Máscara el término negativo*:	${\displaystyle M=00010101\,}$
3. Subtract: ${\displaystyle P-M!$:	${\displaystyle Q=11010101\,}$
*.(Notación binaria firmada con complemento de uno sin complemento de dos)

Si los −1 dígitos de ${\displaystyle Q}$ se almacenan como ceros (0) como es común, entonces ${\displaystyle P}$ es ${\displaystyle Q}$ y computación ${\displaystyle M}$ es trivial: realizar un complemento de uno (bit por bit complemento) en el original ${\displaystyle Q}$.

Q := Q − bit.bnot()Q) -- Apropiado si -1 dígitos en Q están representados como ceros como es común.

Por último, los cocientes computados por este algoritmo son siempre extraños, 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, haga un solo paso restaurador después Q se convierte de forma no estándar a forma estándar:

si R c) 0 entonces Q := Q − 1 R := R + D - Sólo se necesita si el resto es de interés.final si

El resto real es R >> norte. (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).

SRT division

La división SRT es un método popular de división en muchas implementaciones de microprocesadores. El algoritmo lleva el nombre de D. W. Sweeney de IBM, James E. Robertson de la Universidad de Illinois y K. D. 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).

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.

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 ${\displaystyle D}$ y multiplicar ese recíproco por ${\displaystyle N}$ para encontrar último ${\displaystyle Q}$.

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

1. Calcular una estimación ${\displaystyle X_{0}$ para el recíproco ${\displaystyle 1/D}$ del divisor ${\displaystyle D}$.
2. Computa sucesivamente estimaciones más precisas ${\displaystyle X_{1},X_{2},\ldotsX_{S}$ del recíproco. Aquí es donde se emplea el método Newton-Raphson como tal.
3. Computa 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 ${\displaystyle D}$, es necesario encontrar una función ${\displaystyle f(X)}$ que tiene cero ${\displaystyle X=1/D}$. La función obvia es ${\displaystyle f(X)=DX-1}$, pero la iteración Newton-Raphson para esto no es útil, ya que no puede ser computado sin saber ya el recíproco de ${\displaystyle D}$ (Además, intenta calcular la reciprocidad exacta en un paso, en lugar de permitir mejoras iterativas). Una función que funciona es ${\displaystyle f(X)=(1/X)-D}$, por lo que la iteración Newton-Raphson da

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

que puede calcularse ${\displaystyle X_{i}$ usando solamente la multiplicación y la resta, o usando dos multiplicados fusionados.

Desde el punto de vista de la computación, las expresiones ${\displaystyle X_{i+1}=X_{i}+X_{i}(1-DX_{i}}$ y ${\displaystyle X_{i+1}=X_{i}(2-DX_{i}}$ no son equivalentes. Para obtener un resultado con una precisión de 2n bits mientras se hace uso de la segunda expresión, se debe calcular el producto entre ${\displaystyle X_{i}$ y ${\displaystyle (2-DX_{i})}$ con doble precisión dada ${\displaystyle X_{i}$()n bits). En contraste, el producto entre ${\displaystyle X_{i}$ y ${\displaystyle (1-DX_{i})}$ necesidad sólo se computa con una precisión n porque el líder n bits (después del punto binario) de ${\displaystyle (1-DX_{i})}$ son ceros.

Si el error se define como ${\displaystyle \varepsilon ¿Qué?$Entonces:

${\displaystyle {\begin{aligned}\varepsilon - ¿Por qué? ¿Qué?$

Esta oscilación 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 aproximadamente dobles 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 entero grande). Pero también significa que la convergencia inicial del método puede ser comparativamente lenta, especialmente si la estimación inicial ${\displaystyle X_{0}$ es pobremente elegido.

Para el subproblema de elegir una estimación inicial ${\displaystyle X_{0}$, es conveniente aplicar un poco de cambio al divisor D para escalar de modo que 0,5 ≤ D ≤ 1; aplicando el mismo bit-shift al numerador N, uno asegura que el cociente no cambia. Entonces uno podría utilizar una aproximación lineal en la forma

${\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 intervalo ${\displaystyle [0.5,1]}$, uno debe usar

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

Los coeficientes de la aproximación lineal se determinan como sigue. El valor absoluto del error es ${\displaystyle ¦ _{0} tu vida= turba1-D(T_{1}+T_{2}D)$. El valor absoluto máximo del error es determinado por el teorema de equioscillación Chebyshev aplicado a ${\displaystyle F(D)=1-D(T_{1}+T_{2}D)}$. El mínimo local ${\displaystyle F(D)}$ ocurre cuando ${\displaystyle F'(D)=0}$, que tiene solución ${\displaystyle D=-T_{1}/(2T_{2}}$. La función en ese mínimo debe ser de signo opuesto como la función en los puntos finales, es decir, ${\displaystyle F(1/2)=F(1)=F (-T_{1}/(2T_{2})}$. Las dos ecuaciones en los dos desconocidos tienen una solución única ${\displaystyle T_{1}=48/17}$ y ${\displaystyle T_{2}=-32/17}$, y el error máximo es ${\displaystyle F(1)=1/17}$. Usando esta aproximación, el valor absoluto del error del valor inicial es menor que

${\displaystyle \vert \varepsilon ################################################################################################################################################################################################################################################################ {1 \over 17}\approx 0.059.\,}$

Es posible generar un ajuste polinómico de grado mayor que 1, calculando los coeficientes utilizando 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 \,}$

pasos son suficientes para calcular el valor hasta ${\displaystyle P\,}$ Lugares binarios. Esto evalúa a 3 para IEEE una sola precisión y 4 para formatos de doble precisión y doble extensión.

Pseudocódigo

Lo siguiente calcula el cociente de N y D con una precisión de P lugares binarios:

Express D as M × 2e donde 1 ≤ M se realizó 2 (representación de puntos flotantes estándar)
D':= D / 2e+1 // escala entre 0,5 y 1, se puede realizar con cambio de bits / resta exponenteN':= N / 2e+1X:= 48/17 - 32/17 × D' // constantes precomputadoras con la misma precisión que Drepetición ${\displaystyle \left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}$ veces // puede ser precomputado basado en P fijoX:= X + X × (1 - D' × X)
finalRegreso N' × X

Por ejemplo, para una división de doble precisión de punto flotante, este método utiliza 10 multiplicaciones, 9 adiciones y 2 turnos.

Variante de 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}}\derecha). }$

Este es el mejor ajuste cuadrático a 1/D y proporciona 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 bucle se realiza hasta que X coincida con 1/D en sus bits P iniciales, entonces el número de iteraciones no será superior a

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

que es el número de veces 99 debe ser cubierto 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 (según Robert Elliott Goldschmidt) 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}{}{\frac} {\fnK} {\f} {\fnK}}} {\f}}} {\f}}} {\f}}}} {\f}}}}} {\f}}}} {\f}} {\fnMic}}} {\f}}}}}}} {\f}}}}} {\f}}}} {\f}}}} {\f}}} {\f}}}}} {\f}}}}}} {\f}} {\f}}}}} {\f}}}}} {\f} {\f} {\f}}} {\f}}}}}}}}}} {\f}}}}}} {\f} {\f} {\f}}}}}} {\f}}}}}}}}}}}}}}}}}} {\f} {\f} {\f} {\f} {\f}}}}}}}}}}}}}}}}} {\f} {\fnMicrosoft Sans Serif} {\fnMicrosoft Sans Serif} }{F_{\ldots }}}$

Los pasos para la división Goldschmidt son:

1. Generar una estimación para el factor de multiplicación F_i.
2. Multiplique el dividendo y divisor por F_i.
3. Si el divisor está suficientemente cerca de 1, devolver el dividendo, de lo contrario, bucle al paso 1.

Suponiendo que N/D se haya escalado de modo que 0 < D < 1, cada F_i se basa en D:

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

Multiplicar el dividendo y el divisor por el factor produce:

${\displaystyle {\frac {N_{i+1}{D_{i+1}={\frac}}={\frac {\i}}} {\f}}}}} {\f}} {\f}}}} {\f}}} {\f}} {\f}}}}} {\f}}}}}}}}}}}}} {\ {N_{i}{D_} {\fn} {\fnK}}} {\fn}} {\fn}} {\fn}}} {\fn}} {\fn}}}} {\fn}}} {\fn}}}} {\f}}} {\f}}}}} {\f}}}}}}}}} {\f} {\f}}}}}} {\f}}}}}} {\f}} {\f}}}}}}}}} {\f}}} {\f}}}} {\f}}}}}} {\f}}} {\f}}}}}}}}}}} {\f}} {\f}} {\f}}}}} {\f}}} {\f}}}}}}\f}}}}}}}}} {\f}} {\f}}}}}}}}}}}}}}}}}}}}}}}}}} {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. También se conoce como algoritmo Anderson Earle Goldschmidt Powers (AEGP) y lo implementan varios procesadores de IBM. 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.

Teorema del binomio

El método Goldschmidt se puede utilizar con factores que permiten simplificaciones por el teorema binomio. Assume ${\displaystyle N/D}$ ha sido escalada por un poder de dos tales que ${\displaystyle D\in \left({\tfrac {1}{2},1\right]}$. Elegimos ${\displaystyle D=1-x}$ y ${\displaystyle F_{i}=1+x^{2}}$. Este rendimiento

$${\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 n pasos ${\displaystyle \left(x\in \left[0,{\tfrac {1}{2}\right)\right)}$, el denominador ${\displaystyle 1-x^{2^{n}}$ puede ser redondeado 1 con un error relativo

${\displaystyle \varepsilon ¿Qué? ¿Qué?$

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

Métodos de entero grande

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 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 mediante el método de Newton como se describe anteriormente, así como los algoritmos ligeramente más rápidos de división de Burnikel-Ziegler, reducción de Barrett y reducción de Montgomery. 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 punto flotante, el uso de (1/D) presenta pocos problemas, pero en aritmética de enteros el recíproco siempre se evaluará como cero (suponiendo que |D| > 1 ).

No es necesario utilizar específicamente (1/D); cualquier valor (X/Y) que reduce a (1/D) puede ser utilizado. Por ejemplo, para la división en 3, podrían utilizarse los factores 1/3, 2/6, 3/9 o 194/582. En consecuencia, si Y era un poder de dos el paso de división reduciría a un rápido cambio de bits derecho. El efecto de calcular N/D comoN·X)/Y reemplaza una división con un multiplicado y un cambio. Tenga en cuenta que los paréntesis son importantes, como N·(X/Y) evaluará a 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 "lo suficientemente cerca" #34; que el error introducido por la aproximación está en los bits que son descartados por la operación de desplazamiento. 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.

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 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 redondeado hacia arriba. 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). OEIS proporciona secuencias de constantes para la multiplicación como A346495 y para el desplazamiento a la derecha como A346496.

Para general x-bit división de enteros sin firmar donde el divisor D no es un poder de 2, la siguiente identidad convierte la división en dos x-bit add/subtraction, one x-bit by x- multiplicación de bits (donde sólo se utiliza la mitad superior del resultado) y varios cambios, después de precomputación ${\displaystyle k=x+\lceil \log ¿Qué?$ y ${\displaystyle a=\left\lceil {\frac {2}{d}\right\rceil} - ¿Qué?$:

${\displaystyle \left\lfloor {\frac {N}{D}\right\rfloor =\left\lfloor {\frac\left\lfloor Está bien. {2} {k-x-1}}\right\rfloor ¿Dónde? ¿Qué?$

En algunos casos, la división por una constante se puede lograr en menos tiempo con la conversión de la "multiply por una constante" en una serie de cambios y adiciones o subtractos. De particular interés es la división 10, para la cual se obtiene el cociente exacto, con el resto si es necesario.

Error de redondeo

Las operaciones de división pueden introducir errores de redondeo debido a su precisión limitada.