Division Algorithm

A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of 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, non-performing restoring, non-restoring, and 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 and Goldschmidt fall into this category.

Discussion will refer to the form where

  • Q = Quotient
  • N = Numerator (dividend)
  • D = Denominator (divisor).

Read more about Division Algorithm:  Division By Repeated Subtraction, Long Division, Integer Division (unsigned) With Remainder, Slow Division Methods, Large Integer Methods, Division By A Constant, Rounding Error

Famous quotes containing the word division:

    Slow, slow, fresh fount, keep time with my salt tears;
    Yet slower yet, oh faintly gentle springs:
    List to the heavy part the music bears,
    “Woe weeps out her division when she sings.”
    Droop herbs and flowers;
    Fall grief in showers;
    “Our beauties are not ours”:
    Oh, I could still,
    Like melting snow upon some craggy hill,
    Drop, drop, drop, drop,
    Since nature’s pride is, now, a withered daffodil.
    Ben Jonson (1572–1637)