Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Division algorithm
Summary
A division algorithm is an algorithm which, given two integers N and D (respectively the numerator and the denominator), computes their quotient and/or remainder, the result of Euclidean division. Some are applied by hand, while others are employed by digital circuit designs and software.
Division algorithms fall into two main categories: slow division and fast division. Slow division algorithms produce one digit of the final quotient per iteration. Examples of slow division include restoring, non-performing restoring, non-restoring, and SRT division. Fast division methods start with a close approximation to the final quotient and produce twice as many digits of the final quotient on each iteration. Newton–Raphson and Goldschmidt algorithms fall into this category.
Variants of these algorithms allow using fast multiplication algorithms. It results that, for large integers, the computer time needed for a division is the same, up to a constant factor, as the time needed for a multiplication, whichever multiplication algorithm is used.
Discussion will refer to the form , where
N = numerator (dividend)
D = denominator (divisor)
is the input, and
Q = quotient
R = remainder
is the output.
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:
R := N
Q := 0
while R ≥ D do
R := R − D
Q := Q + 1
end
return (Q,R)
The proof that the quotient and remainder exist and are unique (described at Euclidean division) gives rise to a complete division algorithm, applicable to both negative and positive numbers, using additions, subtractions, and comparisons:
function divide(N, D)
if D = 0 then error(DivisionByZero) end
if D < 0 then (Q, R) := divide(N, −D); return (−Q, R) end
if N < 0 then
(Q,R) := divide(−N, D)
if R = 0 then return (−Q, 0)
else return (−Q − 1, D − R) end
end
At this point, N ≥ 0 and D > 0
return divide_unsigned(N, D)
end
function divide_unsigned(N, D)
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.