Mathematic

Division Algorithm

Division Algorithm

Division Algorithm

The dividend is the number we are dividing into. The divisor is the number we are dividing by and the quotient is the answer. A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of division.

We know that: Dividend = Divisor × Quotient + Remainder

Thus, if the polynomial f(x) is divided by the polynomial g(x), and the quotient is q(x) and the remainder is r(x) then

f(x) = g(x) . q(x) + r(x).

Clearly, if the polynomial f(x) is divided by (x – γ), and the quotient q(x) while the remainder is r the

f(x) = (x – γ) . q(x) + r.

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.

The Division Algorithm for Integers

The division algorithm for integers states that given any two integers a and b, with b > 0,  we can find integers q and r such that 0 < r < b and a = bq + r.

The numbers q and r should be thought of as the quotient and remainder that result when b is divided into a. Of course the remainder r is non-negative and is always less that the divisor, b.

Examples:

  • If a = 9 and b = 2, then q = 4 and r = 1.
  • If a = 12 and b = 17, then q = 0 and r = 12.
  • If a = -17 and b = 3, then q = -6 and r = 1.
  • If a = 18 and b = 6, then q = 3 and r = 0.

Division Algorithm for Polynomials

If p(x) and g(x) are any two polynomials with

g(x) ≠ 0, then we can find polynomials q(x) and r(x) such that

p(x) = q(x) × g(x) + r(x)

where r(x) = 0 or degree of r(x) < degree of g(x).

The result is called Division Algorithm for polynomials.

Dividend = Quotient × Divisor + Remainder

 

Information Source: