Division algorithm: Difference between revisions

Revision as of 02:35, 3 November 2023

Revision as of 16:14, 11 December 2023

Line 1:

{{Short description|Method for division with remainder}}

{{about|algorithms for division of integers|the pencil-and-paper algorithm|Long division|the theorem proving the existence of a unique quotient and remainder|Euclidean division|the division algorithm for polynomials|Polynomial long division}}

A '''division algorithm''' is an [[algorithm]] which, given two integers[[integer]]s ''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 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.<ref>{{cite tech report |title=Software Integer Division |first=Thomas L.| last=Rodeheffer| publisher= Microsoft Research, Silicon Valley|date=2008-08-26 |url=https://www.microsoft.com/en-us/research/wp-content/uploads/2008/08/tr-2008-141.pdf}}</ref> [[#Newton–Raphson division|Newton–Raphson]] and [[#Goldschmidt division|Goldschmidt]] algorithms fall into this category.