Implementación de algoritmos de teoría de números/Algoritmo de división
Ir a la navegación
Ir a la búsqueda
División mediante sustracción repetida[editar]
El más simple de los algoritmos de división, 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 de dos números enteros positivos dados usando solo sustracciones y comparaciones:
while N ≥ D do
N := N − D
end
return N
Modificando este algoritmo para contar las sustracciones que se realizan se puede hallar el cociente, junto al resto que ya se obtenía.
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 return (−Q − 1, D − R) end
end
-- At this point, N ≥ 0 and D > 0
return divide_unsigned(N, D)
end
function divide_unsigned(N, D)
Q := 0; R := N
while R ≥ D do
Q := Q + 1
R := R − D
end
return (Q, R)
end
Este procedimiento siempre devuelve R ≥ 0. A pesar de ser simple, toma Ω(Q) pasos, así que es exponencialmente más lento que incluso lo más lentes algoritmos de división como la división larga. Es útil si Q es pequeño.