Division algorithm: Difference between revisions

Revision as of 16:14, 18 March 2017

Revision as of 09:54, 13 April 2017

Line 1:

{{about|algorithms for division|the theorem proving the existence of a unique quotient and remainder|Euclidean division}}

A '''division algorithm''' is an [[algorithm]] which, given two integers N and D, computesand their [[quotient]] and/or [[remainder]], the result of [[division (mathematics)|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 division|restoring]], non-performing restoring, [[#Non-restoring division|non-restoring]], and [[#SRT division|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 division|Newton–Raphson]] and [[#Goldschmidt division|Goldschmidt]] fall into this category.