Division 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.

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.

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.

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 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.

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.

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:

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.

: 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.

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–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.

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.

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

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.

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).

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

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.

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 – 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.

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

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.

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