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:
“Slow, slow, fresh fount, keep time with my salt tears;
Yet slower yet, oh faintly gentle springs:
List to the heavy part the music bears,
“Woe weeps out her division when she sings.”
Droop herbs and flowers;
Fall grief in showers;
“Our beauties are not ours”:
Oh, I could still,
Like melting snow upon some craggy hill,
Drop, drop, drop, drop,
Since nature’s pride is, now, a withered daffodil.”
—Ben Jonson (1572–1637)
“What other words, we may almost ask, are memorable and worthy to be repeated than those which love has inspired? It is wonderful that they were ever uttered. They are few and rare indeed, but, like a strain of music, they are incessantly repeated and modulated by the memory. All other words crumble off with the stucco which overlies the heart. We should not dare to repeat these now aloud. We are not competent to hear them at all times.”
—Henry David Thoreau (1817–1862)