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. 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 , 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 , el algoritmo calcula de modo que , con :

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: y , , Compárese: en el procedimiento divide_unsigned, el denominador debe ser estrictamente positivo. 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 .

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:

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

J (m, n, q): Si rm = rn, 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 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

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

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=11002 (1210) y D=1002 (410)

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=112 (310) 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

donde: Rj 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, lo que potencialmente reduce el número de operaciones hasta a la mitad y permite una ejecución más rápida. 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:1. Formar el término positivo:2. Enmascarar el término negativo:3. Sustraer: :

Si los dígitos -1 de se almacenan como ceros (0), como es habitual, entonces es y el cálculo de es trivial: se realiza un complemento a uno (complemento bit a bit) sobre el 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, . 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. 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).

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.