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:
“Imperialism is capitalism at that stage of development at which the dominance of monopolies and finance capitalism is established; in which the export of capital has acquired pronounced importance; in which the division of the world among the international trusts has begun, in which the division of all territories of the globe among the biggest capitalist powers has been completed.”
—Vladimir Ilyich Lenin (1870–1924)
“When we awoke, we found a heavy dew on our blankets. I lay awake very early, and listened to the clear, shrill ah, te te, te te, te of the white-throated sparrow, repeated at short intervals, without the least variation, for half an hour, as if it could not enough express its happiness. Whether my companions heard it or not, I know not, but it was a kind of matins to me, and the event of the forenoon.”
—Henry David Thoreau (1817–1862)