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:
“O, if you raise this house against this house
It will the woefullest division prove
That ever fell upon this cursed earth.”
—William Shakespeare (1564–1616)
“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)