Algoritmo de división

Un algoritmo de división es un procedimiento 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 euclídea. Algunos de estos procedimientos están ideados para realizar el cálculo manualmente, mientras que otros forman parte de programas de ordenador o están incorporados al diseño de circuitos digitales.

Los algoritmos de división se clasifican 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 improductiva, la no 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 de Goldschmidt entran en esta categoría.

Las variantes de estos algoritmos permiten utilizar algoritmos de multiplicación rápidos. Resulta 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á a la fórmula $N/D=(Q,R)$ , donde

N = numerador (dividendo)
D = denominador (divisor)

son la entrada, y

Q = cociente
R = resto

son el resultado.

División por resta repetida

El algoritmo de división más simple, históricamente incorporado en un algoritmo para obtener el 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:

function divide_unsigned(N, D)
    if D= 0 then error(DivisionByZero) end
    R := N
    Q := 0
    while R ≥ D do
        R := R − D
        Q := Q + 1
    end
    return (Q, R)
end

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

function divide(N, D)
  if D= 0 then error(DivisionByZero) end
  if D < 0 then 
    (Q, R) := divide(N, −D)
     return (−Q, R) 
  end
  if N < 0 then
    (Q, R) := divide(−N, D)
    if R= 0 then 
        return (−Q, 0)
    else
        -- Ejemplo: N= -7, D= 3
        -- divide(-N, D)= divide(7, 3)= (2, 1)
        -- R ≠ 0, so return (-2 - 1, 3 - 1)= (-3, 2)
        -- Check: (-3)*3 + 2= -7
        return (−Q − 1, D − R) 
    end
  end
  -- En este punto, N ≥ 0 y D > 0
  return divide_unsigned(N, D)
end

Este procedimiento siempre produce R ≥ 0. Aunque es muy simple, requiere Ω(Q) pasos, por lo que es exponencialmente más lento que incluso los algoritmos de división lenta como la división larga. Es útil si se sabe que Q es pequeño (siendo un algoritmo sensible al resultado) y puede servir como especificación ejecutable.

Implementación alternativa

Una implementación alternativa incrementa un resto y lo restablece cuando alcanza el divisor.

Para $x,y\in \mathbb {N} _{0}$ , el algoritmo calcula $q,r\,$ de modo que $x=qy+r\,$ , con $0\leq r<y$ :

\operatorname {div} (x,y)=\left\lfloor x/y\right\rfloor

x{\bmod {y}}=x-y\left\lfloor x/y\right\rfloor

Considérese este código en Python:

def divide_unsigned2(numerator: int, denominator: int) -> tuple[int, int]
    quotient: int= 0
    remainder: int= 0
    for _ in range(numerator):
        remainder += 1
        if remainder== denominator:
            quotient += 1
            remainder= 0
    return quotient, remainder

Notas

Casos especiales:

x{\bmod {1}}=0

y
,

x{\bmod {0}}=x

,^[2]

La variable quotient nunca se lee. Por lo tanto, cuando sus asignaciones (resaltadas) se eliminan del código y quotient se elimina de la lista de salida, divide_unsigned2, al igual que divide_unsigned, seguirá calculando $x{\bmod {y}}$ .

Implementación alternativa como máquina de contadores
Una implementación alternativa simple como máquina de contadores (CM) puede basarse en esta implementación alternativa. Las instrucciones de la máquina de contadores son:^[3]^[4]

Z (n): Reemplaza r_n por 0.
S (n): Suma 1 a r_n.

J (m, n, q): Si r_m = r_n, salta a la instrucción q; de lo contrario, continúa con la siguiente instrucción del programa.

El programa de la máquina de contadores es ^[5] y

1: J(1,5,0)
2: S(4)
3: J(4,2,6)
4: S(5)
5: J(0,0,1)
6: S(3)
7: Z(4)
8: S(5)
9: J(0,0,1)

.

Después de que la máquina de contadores finaliza el cálculo con los valores iniciales de los registros R1=N y R2=D (los registros restantes son 0),

el registro R3 contiene el cociente (parte entera) de la división N/D, y

el registro R4 contiene el resto.

División larga

Artículo principal: División larga

La división larga es el algoritmo estándar para dividir números de varias cifras expresados en notación decimal, utilizando 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 paso; estos múltiplos 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 constituye la base del algoritmo de división entera (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 una cifra. La división en bloques, 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 resultar más fácil de comprender. 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 la división larga.

División entera (sin signo) con resto

Véase también: Número binario

El siguiente algoritmo, la versión binaria del conocido método de la 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.

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

Ejemplo

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

Paso 1: Establecer R=0 y Q=0
Paso 2: Tomar 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 (establecer R(0) a N(i))
Paso 5: R < D, por lo que se omite la instrucción

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

Paso 2: Establecer 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 (establecer Q(i) a 1)

Paso 2: Establecer 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 (estableciendo Q(i) en 1)

fin
Q=11₂ (3₁₀) y R=0.

Métodos de división lenta

Los métodos de división lenta se basan en una ecuación de recurrencia estándar^[6]

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

donde:

R_j es el resto parcial j de la división (se incluye el paso R(0) := N(i))
B es la base, generalmente 2 internamente en computadoras y calculadoras
q_{n − (j + 1)} es el dígito del cociente en la posición n-(j+1), donde las posiciones de los dígitos se numeran desde el menos significativo 0 hasta el más significativo n-1
n es el número de dígitos del cociente
D es el divisor

División restaurativa

La división restaurativa opera sobre números fraccionarios de coma fija y se basa en la suposición de que 0 < D < N.

Los dígitos del cociente q se forman a partir del conjunto de dígitos 0 y 1.

El algoritmo básico para la división restaurativa binaria (base 2) es:

R := N
D := D << n             -- R y D requieren el doble de ancho de palabra que N y Q.
for 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 desplazamiento en la representación binaria).
  if R >= 0 then
    q(i) := 1           -- Resultado: bit 1
  else
    q(i) := 0           -- Resultado: bit 0
    R := R + D          -- El nuevo resto parcial es el valor desplazado (restaurado).
  end
end

-- Donde: N= numerador, D= denominador, n= #bits, R= resto parcial, q(i)= bit #i del cociente

La división restaurativa no realizativa es similar a la división restaurativa, excepto en que el valor de 2R se guarda, por lo que D no necesita ser sumado nuevamente en el caso de R < 0.

División no restaurativa

La división no restaurativa 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 del cociente. No hay paso de restauración después de la resta,^[7] lo que potencialmente reduce el número de operaciones hasta a la mitad y permite una ejecución más rápida.^[8] El algoritmo básico para la división binaria (base 2) sin restauración de números no negativos es:

-- Entradas: N (Numerador), D (Denominador)
-- n = número de bits
-- R y D se suelen almacenar en registros de ancho 2n o similar para gestionar los desplazamientos.

R := N                     -- Inicializar el resto

for i= n - 1 .. 0 do       -- Por ejemplo, 31..0 para 32 bits
    -- Desplazar el resto a la izquierda (algebraicamente: 2 * R)
    if R >= 0 then
        R := 2 * R - D;    -- Restar D
        q(i) := 1;         -- Registrar el bit cociente como 1
    else
        R := 2 * R + D;    -- Sumar D (restaurar)
        q(i) := -1;        -- Registrar el bit cociente como -1
    end if
end for

Siguiendo este algoritmo, el cociente se presenta en un formato no estándar que consta de dígitos de -1 y +1. Este formato debe convertirse a binario para obtener el cociente final. Ejemplo:

Convierte el siguiente cociente al conjunto de dígitos {0,1}:
Inicio:	$Q=111{\bar {1}}1{\bar {1}}1{\bar {1}}$
1. Formar el término positivo:	$P=11101010\,$
2. Enmascarar el término negativo:^[9]	$M=00010101\,$
3. Sustraer: $P-M$ :	$Q=11010101\,$

Si los dígitos -1 de $Q$ se almacenan como ceros (0), como es habitual, entonces $P$ es $Q$ y el cálculo de $M$ es trivial: se realiza un complemento a uno (complemento bit a bit) sobre el $Q$ original.

Q := Q − bit.bnot(Q)      -- Es apropiado si los dígitos −1 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 se encuentra en el rango -D < R < D. Por ejemplo, 5 / 2 = 3 R -1. Para convertirlo a un resto positivo, se realiza un único paso de restauración «después» de que Q se haya convertido de la forma no estándar a la forma estándar:

if R < 0 then
  Q := Q − 1
  R := R + D  -- Solo es necesario si el resto es de interés.
end if

El resto real es R >> n. Al igual que con la división de restauración, los bits de menor orden de R se consumen al mismo ritmo que se generan los bits del cociente Q, y es común usar un único registro para ambos.

División SRT

La división SRT es un método popular para la división en muchas implementaciones de microprocesadores.^[10]^[11] El algoritmo recibe su nombre de D. W. Sweeney de IBM, James E. Robertson de Universidad de Illinois Urbana-Champaign y de K. D. Tocher del Imperial College London. 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).^[12]^[13]^[14]

La división SRT es similar a la división no restaurativa, pero utiliza una tabla de consulta basada en el dividendo y el divisor para determinar cada dígito del cociente.

La diferencia más significativa radica en el uso de 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 o +2. Debido a esto, la elección de un dígito del cociente no tiene por qué ser perfecta; los dígitos posteriores pueden corregir pequeños errores. Por ejemplo, los pares de dígitos del cociente (0, +2) y (1, -2) son equivalentes, ya que se trata de 0 × 4 + 2 = 1 × 4 − 2). Esta tolerancia permite seleccionar los dígitos del cociente utilizando solo los bits más significativos del dividendo y el divisor, en lugar de requerir una resta completa. Esta simplificación permite, a su vez, utilizar una base mayor que 2.

Al igual que en la división no restaurativa, los pasos finales consisten en una resta final de ancho completo para resolver el último bit del cociente y la conversión del cociente a formato binario estándar.

El error detectado en el procesador Intel Pentium original, conocido como el error de división del Intel Pentium, se debió a una tabla de búsqueda codificada incorrectamente. Los procesadores Pentium utilizaban una tabla de 2048 celdas, de las cuales 1066 debían rellenarse, y los valores de cinco celdas se omitieron erróneamente.^[15]^[16]^[17]

Métodos de división rápida

División de Newton-Raphson

El método de Newton-Raphson utiliza el método de Newton para hallar el recíproco de $D$ y multiplica ese recíproco por $N$ para hallar el cociente final $Q$ .

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

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

Para aplicar el método de Newton y hallar el recíproco de $D$ , es necesario encontrar una función $f(X)$ que tenga un cero en $X=1/D$ . La función obvia para ello es $f(X)=DX-1$ , pero la iteración de Newton-Raphson para esta no resulta útil, ya que no se puede calcular sin conocer previamente el recíproco de $D$ (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 $f(X)=(1/X)-D$ , para la cual la iteración de Newton-Raphson da como resultado:

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 a partir de $X_{i}$ usando solo multiplicación y resta, o usando dos fusionados multiplicar-sumar.

Desde el punto de vista computacional, las expresiones $X_{i+1}=X_{i}+X_{i}(1-DX_{i})$ y $X_{i+1}=X_{i}(2-DX_{i})$ no son equivalentes. Para obtener un resultado con una precisión de 2n bits utilizando la segunda expresión, se debe calcular el producto entre $X_{i}$ y $(2-DX_{i})$ con el doble de la precisión dada de $X_{i}$ (n bits). En cambio, el producto entre $X_{i}$ y $(1-DX_{i})$ solo necesita calcularse con una precisión de n bits, ya que los n bits iniciales (después del punto binario) de $(1-DX_{i})$ son ceros.

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

{\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}}

Este cuadrado del error en cada paso de iteración, conocido como convergencia cuadrática del método de Newton-Raphson, tiene como efecto que el número de dígitos correctos en el resultado se duplique aproximadamente en cada iteración, una propiedad que resulta extremadamente valiosa cuando los números involucrados tienen muchos dígitos (por ejemplo, en el dominio de los enteros grandes). Sin embargo, también implica que la convergencia inicial del método puede ser relativamente lenta, especialmente si la estimación inicial $X_{0}$ no es la adecuada.

Estimación inicial

Para el subproblema de elegir una estimación inicial $X_{0}$ , conviene aplicar un desplazamiento de bits al divisor D para escalarlo de modo que 0,5 = D = 1. Aplicar el mismo desplazamiento de bits al numerador N garantiza que el cociente no cambie. Una vez dentro de un rango acotado, se puede usar un polinomio simple de aproximación para encontrar una estimación inicial.

El polinomio lineal de aproximación con mínimo error absoluto en el peor de los casos en el intervalo $[0.5,1]$ es:

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

Los coeficientes de aproximación lineal $T_{0}+T_{1}D$ se determinan de la siguiente manera. El valor absoluto del error es $|\varepsilon _{0}|=|1-D(T_{0}+T_{1}D)|$ . El mínimo del valor absoluto máximo del error se determina mediante el teorema de equioscilación de Chebyshov aplicado a $F(D)=1-D(T_{0}+T_{1}D)$ . El mínimo local de $F(D)$ se produce cuando $F'(D)=0$ , cuya solución es $D=-T_{0}/(2T_{1})$ . La función en dicho mínimo debe tener signo opuesto a la función en los extremos, es decir, $F(1/2)=F(1)=-F(-T_{0}/(2T_{1}))$ . Las dos ecuaciones con dos incógnitas tienen una solución única, $T_{0}=48/17$ y $T_{1}=-32/17$ , y el error máximo es $F(1)=1/17$ . Con esta aproximación, el valor absoluto del error respecto al valor inicial es menor que:

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

El mejor ajuste cuadrático a $1/D$ en el intervalo es:

X:={\frac {140}{33}}-{\frac {64}{11}}D+{\frac {256}{99}}D^{2}.

Se elige para que el error sea igual a un polinomio de Chebyshov de tercer orden reescalado de primera especie, y proporciona un valor absoluto del error menor o igual a 1/99. Esta mejora equivale a $\log _{2}(\log 99/\log 17)\approx 0.7$ iteraciones de Newton-Raphson, con un coste computacional inferior a una iteración.

Es posible generar un ajuste polinómico de grado superior a 2, calculando los coeficientes mediante el algoritmo Remez. La desventaja es que la estimación inicial requiere más ciclos computacionales, pero, idealmente, a cambio de menos iteraciones del método de Newton-Raphson.

Dado que para este método la convergencia es exactamente cuadrática, se deduce que, a partir de un error inicial $\varepsilon _{0}$ , $S$ iteraciones proporcionarán una respuesta con una precisión de:

P=-2^{S}\log _{2}\varepsilon _{0}-1=2^{S}\log _{2}(1/\varepsilon _{0})-1

cifras binarias. Los valores típicos son:

Más información

,

...

Dígitos binarios de precisión recíproca
$\varepsilon _{0}$	Iteraciones
$\varepsilon _{0}$	0	1	2	3	4
$1/17$	3.09	7.17	15.35	31.7	64.4
$1/99$	5.63	12.26	25.52	52.03	105.07

Cerrar

Una estimación inicial cuadrática más dos iteraciones es suficientemente precisa para el formato de simple precisión, pero tres iteraciones son insuficientes para alcanzar doble precisión. Una estimación inicial lineal más cuatro iteraciones es suficiente para los formatos de precisión doble y doble extendida.

Pseudocódigo

El siguiente código calcula el cociente de N y D con una precisión de P posiciones binarias:

Expresar D como M × 2e donde 1 ≤ M < 2 (representación estándar de punto flotante)

D' := D / 2e+1 // escala entre 0,5 y 1; se puede realizar con desplazamiento de bits/resta de exponentes

N' := N / 2e+1

X := 48/17 − 32/17 × D' // precalcula constantes con la misma precisión que D

repetir 
  
          ⌈
          
              log
              
                2
              
            ⁡
            
                  P
                  +
                  1
                
                    log
                    
                      2
                    
                  ⁡
                  17
                
          ⌉
        
    {\displaystyle \left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}
  
 veces // se puede precalcular en función de un P fijo

X := X + X × (1 - D' × X)

fin
retornar 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.

Iteración cúbica

Existe una iteración que utiliza tres multiplicaciones para obtener un error cúbico:

\varepsilon _{i}=1-DX_{i}

Y_{i}=X_{i}\varepsilon _{i}

X_{i+1}=X_{i}+Y_{i}+Y_{i}\varepsilon _{i}.

El término Y_ie_i es nuevo.

Ampliando lo anterior, $X_{i+1}$ se puede escribir como:

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

con el resultado de que el término de error:

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

Esto representa 3/2 del cálculo de la iteración cuadrática, pero logra $\log 3/\log 2\approx 1.585$ la misma convergencia, por lo que es ligeramente más eficiente. Dicho de otro modo, dos iteraciones de este método elevan el error a la novena potencia con el mismo coste computacional que tres iteraciones cuadráticas, que solo lo elevan a la octava potencia.

El número de bits correctos después de $S$ iteraciones es: $P=-3^{S}\log _{2}\varepsilon _{0}-1=3^{S}\log _{2}(1/\varepsilon _{0})-1$ cifras binarias. Los valores típicos son:

Más información

,

...

Bits de precisión recíproca
$\varepsilon _{0}$	Iteraciones
$\varepsilon _{0}$	0	1	2	3
$1/17$	3.09	11.26	35.79	109.36
$1/99$	5.63	18.89	58.66	177.99

Cerrar

Una estimación inicial cuadrática más dos iteraciones cúbicas proporciona una precisión suficiente para un resultado de doble precisión IEEE. También es posible utilizar una combinación de iteraciones cuadráticas y cúbicas.

El uso de al menos una iteración cuadrática garantiza que el error sea positivo, es decir, que el recíproco se subestime.^[18]^: 370 Esto puede simplificar un paso de redondeo posterior si se requiere un cociente redondeado con precisión.

El uso de polinomios de mayor grado, ya sea en la inicialización o en la iteración, reduce el rendimiento, puesto que las multiplicaciones adicionales necesarias se aprovecharían mejor realizando más iteraciones.

División de Goldschmidt

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

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:

Generar una estimación para el factor de multiplicación F_i.
Multiplicar el dividendo y el divisor por F_i.

Si el divisor está suficientemente cerca de 1, devuelve el dividendo; de lo contrario, vuelve al paso 1.

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

F_{i+1}=2-D_{i}.

Multiplicando el dividendo y el divisor por el factor se obtiene:

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

Tras un número suficiente k de iteraciones, $Q=N_{k}$ .

El método de Goldschmidt se utiliza en las CPU Athlon de Advanced Micro Devices y modelos posteriores,^[21]^[22] También se conoce como algoritmo de Anderson Earle Goldschmidt Powers (AEGP) y se utiliza en varios procesadores de IBM.^[23]^[24] Aunque converge al mismo ritmo que una implementación de Newton-Raphson, una ventaja del método de Goldschmidt es que las multiplicaciones en el numerador y en el denominador se pueden realizar en paralelo.^[24]

Teorema del binomio

El método de Goldschmidt se puede usar con factores que permiten simplificaciones mediante el teorema del binomio.

Supóngase que ⁠ $N/D$ ⁠ se ha escalado por una potencia de dos tal que $D\in \left({\tfrac {1}{2}},1\right]$ .

Se eligen $D=1-x$ y $F_{i}=1+x^{2^{i}}$ .

Esto da como resultado:

{\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}}

.

Tras $n$ pasos de $\left(x\in \left[0,{\tfrac {1}{2}}\right)\right)$ , el denominador $1-x^{2^{n}}$ se puede redondear a 1 con un error de aproximación:

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

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

Métodos para enteros grandes

Los métodos diseñados para su implementación en hardware generalmente no escalan a enteros con miles o millones de dígitos decimales. Estos se presentan con frecuencia, por ejemplo, en las reducciones modulares utilizadas en criptografía. Para estos enteros grandes, algoritmos de división más eficientes transforman el problema para utilizar un número reducido de multiplicaciones, que luego se pueden realizar utilizando un algoritmo de multiplicación asintóticamente eficiente como el algoritmo de Karatsuba, el algoritmo 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 (salvo una constante multiplicativa) que el de la multiplicación. Ejemplos incluyen la reducción a la multiplicación por el método de Newton,^[25] así como los algoritmos ligeramente más rápidos de la división de Burnikel-Ziegler,^[26] la reducción de Barrett y la reducción de Montgomery.^[27]^{[verifica la fuente]} El método de Newton es particularmente eficiente en escenarios donde se 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 inverso.

Dado que 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 sola 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 la aritmética de coma flotante, el uso de (1/D) presenta pocos problemas, ^[28], pero en la aritmética entera, el recíproco siempre será cero (suponiendo que |D| > 1).

No es necesario usar específicamente (1/D), y se puede usar cualquier valor (X/Y) que se reduzca a (1/D). Por ejemplo, para la división por 3, se podrían usar los factores 1/3, 2/6, 3/9 o 194/582. En consecuencia, si Y fuera una potencia de dos, el paso de división se reduciría a un desplazamiento rápido de bits a la derecha. El efecto de calcular N/D como (N·X)/Y reemplaza una división por una multiplicación y un desplazamiento. Nótese que los paréntesis son importantes, ya que N·(X/Y) se evaluaría como cero.

Sin embargo, a menos que D sea una potencia de dos, no existe 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 sí lo suficientemente cercano como para que el error introducido por la aproximación se encuentre en los bits que se descartan durante la operación de desplazamiento.^[29]^[30]^[31] La reducción de Barrett utiliza potencias de 2 para el valor de Y para que la división por Y sea un simple desplazamiento a la derecha. ^[33]

Como ejemplo concreto de coma fija, para enteros sin signo de 32 bits, la división por 3 se puede reemplazar por una multiplicación por 2863311531/2³³, una multiplicación ampliada por 2863311531 (sistema hexadecimal 0xAAAAAAAB) seguida de un desplazamiento de 33 bits a la derecha. El valor de 2863311531 se calcula como 2³³/3 y luego se redondea al alza. De igual modo, la división por 10 se puede expresar como una multiplicación por 3435973837 (0xCCCCCCCD) seguida de una división por 2³⁵ (o un desplazamiento de 35 bits a la derecha).^[34]^: p230-234 OEIS proporciona secuencias de las constantes para la multiplicación como (sucesión A346495 en OEIS) y para el desplazamiento a la derecha como (sucesión A346496 en OEIS).

Para la división general de enteros sin signo $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 se utiliza la mitad superior del resultado) y varios desplazamientos, tras precalcular $k=x+\lceil \log _{2}{D}\rceil$ y $a=\left\lceil {\frac {2^{k}}{D}}\right\rceil -2^{x}$ :

\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{donde }}b=\left\lfloor {\frac {Na}{2^{x}}}\right\rfloor

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

Error de redondeo

Al realizar una división, los valores exactos del cociente, $q$ y del resto $r$ se aproximan para ajustarse a los límites de precisión del ordenador. El algoritmo de división establece que:

[a=bq+r]

donde $0\leq r<|b|$ .

En coma flotante, el cociente $q$ se representa como ${\tilde {q}}$ y el resto $r$ como ${\tilde {r}}$ , introduciendo errores de redondeo, $\epsilon _{q}$ y $\epsilon _{r}$ :

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

Este redondeo provoca un pequeño error que puede propagarse y acumularse en cálculos posteriores. Dichos errores son especialmente pronunciados en procesos iterativos y al restar valores casi iguales, como se indica en pérdida de significancia. Para mitigar estos errores, se emplean técnicas como el uso de un dígito de guarda o mayor precisión (o precisión arbitraria).^[37]^[38]