Division algorithm

Newton–Raphson divisionSRT divisiondivision by a constantNon-restoring divisionRestoring divisionSRTSRT Division algorithmDivideFast Division AlgorithmGoldschmidt iteration
A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division.wikipedia
68 Related Articles

Algorithm

algorithmsalgorithm designcomputer algorithm
A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division.
Arithmetic algorithms, such as a division algorithm, was used by ancient Babylonian mathematicians c. 2500 BC and Egyptian mathematicians c. 1550 BC.

Euclidean division

Division theoremdividedivisible by two without remainder
A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division.
The methods of computation are called integer division algorithms, the best known of which being long division.

Greatest common divisor

gcdcommon factorgreatest common factor
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:
A much more efficient method is the Euclidean algorithm, which uses a division algorithm such as long division in combination with the observation that the gcd of two numbers also divides their difference.

Long division

(long)Division tableauSchoolbook long division
The following algorithm, the binary version of the famous long division, will divide N by D, placing the quotient in Q and the remainder in R.
In arithmetic, long division is a standard division algorithm suitable for dividing multi-digit numbers that is simple enough to perform by hand.

Short division

Short division is an abbreviated form of long division suitable for one-digit divisors.
In arithmetic, short division is a division algorithm which breaks down a division problem into a series of easy steps.

Remainder

in remainderlaver
A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division.
See Euclidean division for a proof of this result and division algorithm for algorithms describing how to calculate the remainder.

Output-sensitive algorithm

output-sensitiveoutput-sensitive algorithms
It is useful if Q is known to be small (being an output-sensitive algorithm), and can serve as an executable specification.
A simple example of an output-sensitive algorithm is given by the division algorithm division by subtraction which computes the quotient and remainder of dividing two positive integers using only addition, subtraction, and comparisons:

Multiplication algorithm

long multiplicationfast multiplicationFFT multiplication
Variants of these algorithms allow using fast multiplication algorithms.
Multiplication by a constant and division by a constant can be implemented using a sequence of shifts and adds or subtracts.

Multiply–accumulate operation

fused multiply–addmultiply–accumulateMAC
: which can be calculated from X_i using only multiplication and subtraction, or using two fused multiply–adds.
A useful benefit of including this instruction is that it allows an efficient software implementation of division (see division algorithm) and square root (see methods of computing square roots) operations, thus eliminating the need for dedicated hardware for those operations.

Multiplicative inverse

reciprocalinversereciprocals
Newton–Raphson uses Newton's method to find the reciprocal of D and multiply that reciprocal by N to find the final quotient Q.
Computing the reciprocal is important in many division algorithms, since the quotient a/b can be computed by first computing 1/b and then multiplying it by a.

Newton's method

Newton–Raphson methodNewton-RaphsonNewton–Raphson
Newton–Raphson uses Newton's method to find the reciprocal of D and multiply that reciprocal by N to find the final quotient Q. Examples include reduction to multiplication by Newton's method as described above, as well as the slightly faster Barrett reduction and Montgomery reduction algorithms.
An important application is Newton–Raphson division, which can be used to quickly find the reciprocal of a number, using only multiplication and subtraction.

Two's complement

2's complementtwo's-complementtwo's complement notation

Montgomery modular multiplication

Montgomery reductionMontgomery multiplicationMontgomery multiplier
Examples include reduction to multiplication by Newton's method as described above, as well as the slightly faster Barrett reduction and Montgomery reduction algorithms.
. One conditional final subtraction reduces this to less than N. This procedure has a better computational complexity than standard division algorithms, since it avoids the quotient digit estimation and correction that they need.

Pentium FDIV bug

Thomas NicelyFDIVFDIV bug
The Intel Pentium processor's infamous floating-point division bug was caused by an incorrectly coded lookup table.

Barrett reduction

Examples include reduction to multiplication by Newton's method as described above, as well as the slightly faster Barrett reduction and Montgomery reduction algorithms.
would be to use a fast division algorithm.

Floating-point arithmetic

floating pointfloating-pointfloating-point number
In floating-point arithmetic the use of (1/D) presents little problem, but in integer arithmetic the reciprocal will always evaluate to zero (assuming |D| > 1).
In practice, the way these operations are carried out in digital logic can be quite complex (see Booth's multiplication algorithm and Division algorithm).

Quotient

A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division.

Computational complexity

complexitycomputational burdenamount of computation
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.

Euclid's Elements

ElementsEuclid's ''ElementsEuclid
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:

Chunking (division)

Chunking
Chunking – also known as the partial quotients method or the hangman method – is a less-efficient form of long division which may be easier to understand.

Microprocessor

microprocessorsprocessorprocessors
Named for its creators (Sweeney, Robertson, and Tocher), SRT division is a popular method for division in many microprocessor implementations.

Lookup table

lookuplook-up tabletable lookup
SRT division is similar to non-restoring division, but it uses a lookup table based on the dividend and the divisor to determine each quotient digit.

P5 (microarchitecture)

PentiumP5Pentium MMX
The Intel Pentium processor's infamous floating-point division bug was caused by an incorrectly coded lookup table.