Division algorithm

A division algorithm is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> which, given two <a href="/facts/Integer/PUwwrawx">integers</a> N and D (respectively the numerator and the denominator), computes their <a href="/facts/Quotient/JekSq1Ko">quotient</a> and/or <a href="/facts/Remainder/wCmbYeeh">remainder</a>, the result of <a href="/facts/Euclidean_division/hgNk37et">Euclidean division</a>. 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 <a href="/facts/Multiplication_algorithm/68xf6EdK">multiplication algorithms</a>. It results that, for large integers, the <a href="/facts/Computational_complexity/Qenh22Ja">computer time</a> 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 
 
 
 
 N
 
 /
 
 D
 =
 (
 Q
 ,
 R
 )
 
 
 {\displaystyle N/D=(Q,R)}
 
, where

<ul><li>N = <a href="/facts/Fraction/ghnQE9B3">numerator</a> (dividend)</li>
<li>D = <a href="/facts/Fraction/ghnQE9B3">denominator</a> (divisor)</li></ul>
is the input, and

<ul><li>Q = <a href="/facts/Quotient/JekSq1Ko">quotient</a></li>
<li>R = <a href="/facts/Remainder/wCmbYeeh">remainder</a></li></ul>
is the output.

Division algorithm open-in-new

Division algorithm