Division By Repeated Subtraction
The simplest division algorithm, historically incorporated into a greatest common divisor algorithm presented in Euclid's Elements, Book VII, Proposition 1, finds the remainder given two positive integers using only subtractions and comparisons:
while N ≥ D do N := N - D
end
return N
The proof that the quotient and remainder exist and are unique, described at Euclidean division, gives rise to a complete division algorithm using additions, subtractions, and comparisons:
function divide(N, D) if D == 0 then throw DivisionByZeroException end if D < 0 then (Q,R) := divide(N, -D); return (-Q, R) end if N < 0 then (Q,R) := divide(-N, D); return (-Q - 1, D - R) end // At this point, N ≥ 0 and D > 0 Q := 0; R := N while R ≥ D do Q := Q + 1 R := R - D end return (Q, R)
end
This procedure always produces R ≥ 0. Although very simple, it takes Ω(Q) steps, and so is exponentially slower than even slow division algorithms like long division. It is useful if Q is known to be small (being an output-sensitive algorithm), and can serve as an executable specification.
Read more about this topic: Division Algorithm
Famous quotes containing the words division and/or repeated:
“If the technology cannot shoulder the entire burden of strategic change, it nevertheless can set into motion a series of dynamics that present an important challenge to imperative control and the industrial division of labor. The more blurred the distinction between what workers know and what managers know, the more fragile and pointless any traditional relationships of domination and subordination between them will become.”
—Shoshana Zuboff (b. 1951)
“Nothing in the nature around us is evil. This needs to be repeated since one of the human ways of talking oneself into inhuman acts is to cite the supposed cruelty of nature.”
—John Berger (b. 1926)