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:
“Don’t order any black things. Rejoice in his memory; and be radiant: leave grief to the children. Wear violet and purple.... Be patient with the poor people who will snivel: they don’t know; and they think they will live for ever, which makes death a division instead of a bond.”
—George Bernard Shaw (1856–1950)
“It is commonly said ... that ridicule is the best test of truth; for that it will not stick where it is not just. I deny it. A truth learned in a certain light, and attacked in certain words, by men of wit and humour, may, and often doth, become ridiculous, at least so far, that the truth is only remembered and repeated for the sake of the ridicule.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)