Integer Division

Of all the elemental operations, division is the most complicated and can consume the most resources (in either silicon, to implement the algorithm in hardware, or in time, to implement the algorithm in software). In many computer applications, division is less frequently used than addition, subtraction or multiplication. As a result, some microprocessors that are designed for digital signal processing (DSP) or embedded processor applications do not have a divide instruction (they also usually omit floating point support as well).

Recently I did some preliminary work on the design of the code generation phase for a compiler that would target a digital signal processor. This processor does not have a divide instruction and I had no idea how long it would take to implement the run time function needed to support integer division in software. The answer, it turns out, is "it depends". If all that is needed is a basic division function, and performance is not a major issue, the runtime function is fairly straight forward. A high performance division function is more complicated and would take more time to implement and test. The division function that is included here is of the former variety - a basic binary integer division function. I have also included some references on higher performance algorithms, but these are, as my professors used to say, left as exercises to the reader.

The integer division algorithm included here is a so called "radix two" division algorithm. One computation step is needed for each binary digit. There are radix 4, 8, 16 and even 256 algorithms, which are faster, but are more difficult to implement. The main reference I used in implementing my algorithm was Digital Computer Arithmetic by Cavanaugh. Several other references on high radix division are also listed below.

My integer division algorithm is written in C++ and is included below. The file can be downloaded here.

Division is the process of repeated subtraction. Like the long division we learned in grade school, a binary division algorithm works from the high order digits to the low order digits and generates a quotient (division result) with each step. The division algorithm is divided into two steps:

  1. Shift the upper bits of the dividend (the number we are dividing into) into the remainder.

  2. Subtract the divisor from the value in the remainder. The high order bit of the result become a bit of the quotient (division result). 

/*
   Copyright stuff

   Use of this program, for any purpose, is granted the author,
   Ian Kaplan, as long as this copyright notice is included in
   the source code or any source code derived from this program.
   The user assumes all responsibility for using this code.

   Ian Kaplan, October 1996

*/


void unsigned_divide(unsigned int dividend,
		     unsigned int divisor,
		     unsigned int &quotient,
		     unsigned int &remainder )
{
  unsigned int t, num_bits;
  unsigned int q, bit, d;
  int i;

  remainder = 0;
  quotient = 0;

  if (divisor == 0)
    return;

  if (divisor > dividend) {
    remainder = dividend;
    return;
  }

  if (divisor == dividend) {
    quotient = 1;
    return;
  }

  num_bits = 32;

  while (remainder < divisor) {
    bit = (dividend & 0x80000000) >> 31;
    remainder = (remainder << 1) | bit;
    d = dividend;
    dividend = dividend << 1;
    num_bits--;
  }


  /* The loop, above, always goes one iteration too far.
     To avoid inserting an "if" statement inside the loop
     the last iteration is simply reversed. */

  dividend = d;
  remainder = remainder >> 1;
  num_bits++;

  for (i = 0; i < num_bits; i++) {
    bit = (dividend & 0x80000000) >> 31;
    remainder = (remainder << 1) | bit;
    t = remainder - divisor;
    q = !((t & 0x80000000) >> 31);
    dividend = dividend << 1;
    quotient = (quotient << 1) | q;
    if (q) {
       remainder = t;
     }
  }
}  /* unsigned_divide */



#define ABS(x)  ((x) < 0 ? -(x) : (x))



void signed_divide(int dividend,
		   int divisor,
		   int &quotient,
		   int &remainder )
{
  unsigned int dend, dor;
  unsigned int q, r;

  dend = ABS(dividend);
  dor  = ABS(divisor);
  unsigned_divide( dend, dor, q, r );

  /* the sign of the remainder is the same as the sign of the dividend
     and the quotient is negated if the signs of the operands are
     opposite */
  quotient = q;
  if (dividend < 0) {
    remainder = -r;
    if (divisor > 0)
      quotient = -q;
  }
  else { /* positive dividend */
    remainder = r;
    if (divisor < 0)
      quotient = -q;
  }
  
} /* signed_divide */

Ian Kaplan
October, 1996