Implementación de algoritmos de teoría de números/Algoritmo de división

De Wikilibros, la colección de libros de texto de contenido libre.

Descripción formal[editar]

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:

función 
  mientras  hacer
      
  devolver 

Modificando este algoritmo para contar las sustracciones que se realizan se puede hallar el cociente, junto al resto que ya se obtenía.

función 
  
  
  mientras  hacer
     
     
  devolver 

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 lentos algoritmos de división como la división larga. Es útil si q es pequeño.

Implementación en distintos lenguajes de programación[editar]

Lua[editar]

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